# Rerandomizable ElGamal

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.

**Implementation.** I implemented this scheme in Java using the Bouncy Castle library. Feel free to give it a shot! Here is the implementation. You can find some examples in the tests.