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