2
$\begingroup$

I am generating large prime numbers to create a cyclic group for ElGamal encryption, I can specify the bit-length n but want to limit the size because this will ultimately allow me to limit the amount of data passed through external channels.

Also the data being protected has an extremely short time-value vector meaning after a short amount of time the data will become useless to anyone who might manage to decrypt or get access to it(Not sure if there is an official word for that).

What size of a prime number should be used for the cyclic group in this circumstance. The ElGamal keys themselves will also be highly temporary in this setup(can be thrown away almost immediately after a few messages). Is 2048 bit necessary?

Maybe another way of phrasing it:

How much time can n bitlength of an ElGamal cipher-text (assuming the encrypted data is a large mostly random string) buy me(Assuming there is an attacker) before the attacker can potentially crack the encryption? What are some estimates for bitlength n as relating to crack time?

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ Is there a specific reason you need to use El Gamal? Would you consider another public key encryption method (as long is it meets your 'ciphertext isn't too big' requirement)? $\endgroup$
    – poncho
    Commented Apr 14, 2023 at 20:08
  • $\begingroup$ The main reason is because I have implemented an ElGamal protocol already, but I would be open to your suggestions as to alternatives. But I still would like to get an answer to the ElGamal specific case. $\endgroup$
    – Poseidon
    Commented Apr 14, 2023 at 20:11
  • 2
    $\begingroup$ Caveat: textbook ElGamal encryption in $\mathbb Z_p^*$ leaks one bit of information about the plaintext: it's Legendre symbol. That could well allow recognizing the plaintext Yes from No. This and other mistakes have often crept: this concludes "20 out of the 26 analyzed libraries may leak one bit of information". Also ElGamal does not give authenticated encryption. If performance or cryptogram size matters, consider libsodium. $\endgroup$
    – fgrieu ♦
    Commented Apr 17, 2023 at 13:07
  • 1
    $\begingroup$ In my specific case the plain text to encrypt will be several 256 bit scalar integers not a small text like yes or no. Leaking one bit of information is ok in my circumstance as the messages will only carry relevance for a short period of time. This leakage is relevant in this case: "and therefore, may endanger the validity of an election". This does not align with my use case as the results of the messages will be irrelevant very shortly after they are sent. Hence why I am trying to effectively determine the bitlength that would optimize this time-value vector $\endgroup$
    – Poseidon
    Commented Apr 17, 2023 at 18:27
  • $\begingroup$ In the simplest case, without authentication, MITM protection or message integrity, you can publish a 256-bit ephemeral EC public key, and then encrypt the payload by XORing it with an HKDF output of the same length as the payload (using the ECDH shared secret as the IKM). It's not clear from your question exactly what protections you need. $\endgroup$
    – knaccc
    Commented Apr 17, 2023 at 20:33

1 Answer 1

Reset to default
2
+50
$\begingroup$

Sticking to the question as asked, that is choice of modulus size for textbook ElGamal encryption in a multiplicative (sub) group modulo a (perhaps safe) prime, the latest and most relevant data point I know is Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé, and Paul Zimmermann's 2020 report of breaking a DLP modulo a 795-bit prime, using ≈3000 core⋅year, ≈80% of which on standard CPUs with 4 GB RAM/core. That's roughly 4 hours of the Fugaku supercomputer (selected because it's not GPU-centric thus relatively suitable for the job).

The question states

after a short amount of time the data will become useless

but we are left in the dark about what 4 hours is compared to that, and what resources the adversaries have.

Wildly ignoring the $o(1)$ term in the asymptotic formula there, the bit sizes $b$ for a relative difficulty $2^d$ compared to that 795-bit data point would be:

b  582  601  621  642  662  683  705  727  749  772  795  819  842  867  892  917  942  968  995 1022 1049 1105 1163 1222 1283 1346 1411 1478 1547 1617 1690 1764 1840 1919 1999 2081
d  -10   -9   -8   -7   -6   -5   -4   -3   -2   -1    0   +1   +2   +3   +4   +5   +6   +7   +8   +9  +10  +12  +14  +16  +18  +20  +22  +24  +26  +28  +30  +32  +34  +36  +38  +40

That is, 582-bit modulus would perhaps be like a thousand (≈210) times less resource intensive or faster at comparable resource, 1346-bit would perhaps be like a million (≈220) times harder/slower.

I stress this is not conservative, thus is imprudent especially if we consider possible algorithmic improvements; and independently, is likely more and more wrong as we venture away from the reference point.

My actual recommendation if size or/and speed matters is to drop groups based on exponentiation modulo a prime, in favor of Elliptic Curve groups; and drop ElGamal encryption in favor of hybrid encryption, perhaps authenticated.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks. A 4 hour window for decryption should be more than enough in the protocol I am constructing. Can any Elliptic Curve groups be used for this purpose? Are you recommending that the hybrid authenticated encryption I use leverages ECC instead of random primes as well? $\endgroup$
    – Poseidon
    Commented Apr 21, 2023 at 19:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.