# ElGamal and Paillier key sizes for short messages

I am using ElGamal and Paillier schemes to encrypt a large number of short messages: typical 4-byte integers. I do this for the homomorphic properties of these schemes.

However, the way the encryptions work, with, say, a 1024-bit key a 4-byte integer will blow up into two values of overall size of 4096 bits or 512 bytes, which is, well, mildly inconvenient :)

As I deducted from examining the ECRYPT II report, the recommended key size for ElGamal is at least 1024 bits. I did not find recommendations for Paillier, though. However, as I understood, these recommendations are typically for larger messages. Hence, some questions:

1. Is there a difference in choosing a key length based on the size of a message?

2. What would be acceptable key sizes in the situation described above for both cryptosystems? If possible, I would like references to analyses I could read.

Bonus question: Let's assume an adversary gets a hold of an array of encrypted integers and tries to crack the encryption. How would he be able to determine whether he found a proper private key or not, if we assume that he is unable to tell a properly decrypted array from a random array?

• going below 1024 bit with ElGamal makes the scheme weak. 512 bit f.ex. can be broken within a week on EC2. (See Logjam). So you can't "save" there. You also can't reduce the output since (AFAIK) and you must use some (long) randomness (128 bit+) to prevent brute-force guessing.
– SEJPM
Jul 18 '15 at 13:06
• to the bonus question: If the key's too small he just breaks the public key and applies the results to the encrypted data.
– SEJPM
Jul 18 '15 at 13:07

You should not use keys smaller than 1024, and even 1024 is considered too small today. However, if you want additive homomorphism, then you can you encrypt with "ElGamal in the exponent" over Elliptic curves. To explain what I mean by this, let $G$ be the base point (generator) for the Elliptic curve group, let $x$ be the ElGamal private key, and let $P=x\cdot G$ be the ElGamal public key. Then, you can encrypt a value $m$ by computing $(r\cdot G,r\cdot P + m \cdot G)$, where $r$ is random.
Note that given $(U_1,V_1) = (r\cdot G, r\cdot P + a \cdot G)$ and $(U_2,V_2)=(s\cdot G, s\cdot P + b\cdot G)$, it follows that $(U_1+U_2,V_1+V_2) = ((r+s)\cdot G,(r+s)\cdot P + (a+b)\cdot G)$. Thus, this is additively homomorphic.
The only problem with this scheme is that you cannot efficiently decrypt, since this requires solving the DLOG problem over Elliptic curves. However, if you are only encrypting 4 byte integers, then you can brute force decryption using the private key as follows: given $(U,V)$, for every $a$ check if $V=x\cdot U + a\cdot G$. If yes, then you know that this is an encryption of $a$. Now, this will take $2^{32}$ time which is too long. However, you can use this idea and run a generic DLOG algorithm that takes square-root time (e.g., Pollard's rho algorithm) to do this in time $2^{16}$. It is still expensive, but may be OK for your application (depending on what you want to do).
• For such a limited interval as in the above answer you could also precompute a lookup table of all potential values $a'G$ and then decrypt as $aG=V-xU$ and look it up in the table. So you treat decryption efficiency for memory and a one-time precomputation cost. Jul 20 '15 at 8:36