Additive ElGamal cryptosystem using a finite field

Question

I'm trying to implement a modified version of the ElGamal cryptosystem as specified by Cramer et al. in "A secure and optimally efficient multi-authority election scheme", which possesses additive homomorphism between ciphertexts, as opposed to the original version, which presents multiplicative homomorphism.

The BIG problem (as always) is that the paper is annoyingly scarce on the "small" details. Here's what I have so far:

1. Configuration parameters

   • size of $ p $
   • size of $ q $
   • message space

2. Key generation

   • pick a prime number $ p $ of a given "key size", ensuring that $ p - 1 $ has a large prime factor $ q $ (of a given size)
   • pick $ g $ as a generator of the cyclic group $ \mathbb{Z}_{q}^* $
   • generate a random number, $ s \in \mathbb{Z}_{q} $, and compute $ h = g^s \pmod q $
   • The public key is $ (g, h) $ and the private key is $ (s) $

3. Precomputations

   • Since the scheme requires computing discrete logarithms in order to perform the decryption (see below), the messages must be small so we precompute each $ g^m \pmod q $ and we store them in a lookup table

4. Encryption

   • pick a random value $ \alpha \in \mathbb{Z}_{q} $
   • compute $ (x, y) = (g^{\alpha} \pmod q, h^{\alpha} g^m \pmod q) $

5. Decryption

   • $ y x^{-s} \pmod q \equiv h^{\alpha} g^m g^{-s \alpha} \pmod q \equiv g^{s \alpha} g^m g^{-s \alpha} \pmod q \equiv g^m \pmod q $
   • we use the precomputed lookup table to find the corresponding message, $ m $, for the computed $ g^m \pmod q $

Questions:

1. I'm not sure if the implied modulus of each operation is $ q $, as I added myself to the above formulas. Could someone please clarify this? The paper omits it...
2. If, indeed, the modulus of the operations is $ q $, then I need to add it to the public key, right? If I do this, doesn't the scheme become insecure?
3. Regarding the private key, the paper does not specify the set from which to select it, and I assumed it to be $ \mathbb{Z}_{q} $. Is this correct?
4. what should be the size of $ p $ (in bits) in order to have similar security as provided by RSA 1024?
5. what should be the size (in bits) of the large prime factor of $ p - 1 $?

Answer 1

1. As far as I can tell from your description, the modulus is $p$. To multiply two group elements, you compute $xy \mod p$; because the generator $g$ you choose has period $q$ it'll all work out fine.

2. No, $p$, $q$, and $g$ can (and must) all be public. This is ElGamal, not RSA we're talking about - the security comes from the (presumed) hardness of taking discrete logarithms rather than factoring.

3. Yes.

4. and 5. The Ecrypt report on algorithms and key sizes http://www.ecrypt.eu.org/documents.html is a good place to look. It's not an easy question because it depends on how hard you think it is (and will be in the future) to solve discrete logarithms.

There's an existing, open-source implementation of additive ElGamal (in Python) used in the Helios voting system (http://heliosvoting.org) that you might want to look at.

Answer 2

While I haven't read the paper, I believe I can answer these questions:

1. I'm not sure if the implied modulus of each operation is $q$, as I added myself to the above formulas. Could someone please clarify this? The paper omits it...

No, the arithmetic is done modulo $p$. Remember, you're working in a subgroup of size $q$ of $\mathbb{Z}^*_{p}$; the operation between two members of that subgroup is the operation in the supergroup $\mathbb{Z}^*_{p}$, which is multiplication modulo $p$. Now, if you did arithmetic of exponents, that would be done modulo $q$. However, the above protocol never does.

1. If, indeed, the modulus of the operations is $q$, then I need to add it to the public key, right? If I do this, doesn't the scheme become insecure?

Well, $g$, $p$ and $q$ are group parameters; they need to be shared between people using the key. They could be included in the key, or just be implicitly understood by both sides.

1. Regarding the private key, the paper does not specify the set from which to select it, and I assumed it to be $\mathbb{Z}_{q}$. Is this correct?

That is correct; $g^x \bmod p$ can take up exactly $q$ distinct values.

1. what should be the size of $p$ (in bits) in order to have similar security as provided by RSA 1024?

Well, the best general factorization method (NFS) can be applied to the discrete log problem with roughly the same complexity; this implies that a $p$ of 1024 bits would give you roughly the same level of security.

1. what should be the size (in bits) of the large prime factor of $p−1$?

Well, discrete logs in the subgroup can also be solved in time $O(\sqrt q)$; this implies to make this attack (say) take $O(2^{80})$ time, we need to have $q > 2^{160}$. Now, it is unclear exactly how difficult the discrete log problem is in the supergroup; this implies that it might be a good idea to have a larger $p$ and $q$ than what seems immediately necessary.