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($\tau$): is a probabilistic key generation algorithm that takes as input a security parameter $\tau$, and outputs key pair $(pk,sk)$.
• Enc($pk$, $m$): is a probabilistic encryption function that takes as input public key $pk$ and a message $m$, and outputs a ciphertext pair $(C1, C2)$.
• Dec($sk$, $(C1, C2)$): is a deterministic decryption function that takes as input secret key $sk$ and a ciphertext $(C1, C2)$, and outputs message $m$.
• ReRand($pk$, $(C1, C2)$): is a probabilistic randomization algorithm that takes as input public key $pk$ and a ciphertext $(C1, C2)$, and outputs a randomized ciphertext pair $(C1', C2')$.

Correctness. To show the correctness briefly at the interface level, if we have a key pair $(pk,sk)$ and message $m$, the following statements should hold:

1. $(C1, C2)$ $\stackrel{\$}{\longleftarrow}$ Enc($pk$, $m$)
2. $(C1', C2')$ $\stackrel{\$}{\longleftarrow}$ ReRand($pk$, $(C1, C2)$)
3. $m$ $\longleftarrow$ Dec($sk$, $(C1, C2)$)
4. $m'$$\longleftarrow$ Dec($sk$, $(C1', C2')$)
5. This statement is true: $m = m'$ given that $(C1, C2)\neq(C1', C2')$

More concretly (yet high level), the underpinning algorithm is as follows. Let($\mathbb{G},g,q$) be system parameters such that the DDH problem is hard. $q$ is $\tau$-bit prime:

• KGen($\tau$): $sk\stackrel{\$}{\leftarrow}\mathbb{Z}_q$, $pk\stackrel{}{\leftarrow}g^{sk}$, output $(sk,pk)$
• Enc($pk$, $m$): $r\stackrel{\$}{\leftarrow}\mathbb{Z}_q$, output (${pk}^r,g^{r}m$)
• Dec($sk$, $(C_1, C_2)$): output $m\stackrel{}{\leftarrow}C_2\cdot{C_1}^{-1/sk}$
• ReRand($pk$, $(C_1, C_2)$): $r'\stackrel{\$}{\leftarrow}\mathbb{Z}_q, C'_1\stackrel{}{\leftarrow}C_1\cdot{pk}^{r'}, C'_2\stackrel{}{\leftarrow}C_2\cdot{g}^{r'}$, output $C'\stackrel{\$}{\leftarrow}(C'_1,C'_2)$

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.