Rerandomizable ElGamal

28 Mar 2021 Cryptography, public-key, Security

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:

  1. Enc(, )
  2. ReRand(, )
  3. Dec(, )
  4. Dec(, )
  5. 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.