Additive ElGamal cryptosystem using a finite field 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:


Configuration parameters


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

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

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

Encryption


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

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:


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...
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?
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?
what should be the size of $ p $ (in bits) in order to have similar security as provided by RSA 1024?
what should be the size (in bits) of the large prime factor of $ p - 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.
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.
Yes.
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.