ElGamal and Paillier key sizes for short messages

Question

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?

Answer 1

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).

Using Elliptic curves, the size of your ciphertext can be significantly reduced. E.g., with curve P256, you can hold a ciphertext in just over 512 bits.