I recently developed a re-randomizable version of the El-Gamal public-key encryption scheme based on what I have read in this paper written by Anja Lehmann. The classic ElGamal scheme is CPA secure with homomorphic properties, useful in scenarios where we struggle with passive adversaries.
The re-randomizable instantiation of ElGmal should have the following interface:
- KGen(): is a probabilistic key generation algorithm that takes as input a security parameter , and outputs key pair .
- Enc(, ): is a probabilistic encryption function that takes as input public key and a message , and outputs a ciphertext pair .
- Dec(, ): is a deterministic decryption function that takes as input secret key and a ciphertext , and outputs message .
- ReRand(, ): is a probabilistic randomization algorithm that takes as input public key and a ciphertext , and outputs a randomized ciphertext pair .
Correctness. To show the correctness briefly at the interface level, if we have a key pair and message , the following statements should hold:
- Enc(, )
- ReRand(, )
- Dec(, )
- Dec(, )
- This statement is true: given that
More concretly (yet high level), the underpinning algorithm is as follows. Let() be system parameters such that the DDH problem is hard. is -bit prime:
- KGen(): , , output
- Enc(, ): , output ()
- Dec(, ): output
- ReRand(, ): , output
When reading a paper or book, I hate those authors who leave the correctness as an exercise for the readers. However, since this is not really my work and my intension is to share the implementation, I leave the actual correctness as an exercise for you; it’s not that hard though.