Is it possible to contract NIZK proof that a cipher was randomised?

Suppose Alice creates a cipher $c = \text{Enc}(m,r)$ and ZK proof that $c$ was formed correctly (for example, $\text{Enc}$ could be the lifted ElGamal encryption function). Bob wants to randomise $c$ and construct $c' = c\cdot \text{Enc}(0,r')$. How can Bob prove that $c'$ was indeed computed correctly?

Thank you!


There is a very simple way using proofs of discrete logarithms equality and ElGamal encryption. Let me first recall the following sigma proof of equality of to discret logarithms:

Let $G$ be a prime order group, and let $(a,b,c,d)\in G^4$ be such that there exists $x$ such that $a^x=c$ and $b^x=d$. Let a prover that knows $x$ and that want to prove to a verifier that $\log_a(c) = \log_b(d)$

  • The prover chooses $r$ and computes $A=a^r$ and $B=b^r$, then he sends $(A,B)$ to the verifier.

  • The verifier chooses a random $e$ and sends it to the prover. In order to turn it into a non-interactive proof, $e$ can be generated from the hash $H(a||b||c||d||A||B)$ in the random oracle model.

  • The prover returns $z= r + xe$ to the verifier.

  • The verifier checks that $a^z=Ac^e$ and $b^z=Bd^e$.

Well, we then show how to use this proof to prove that some ciphertext $c'$ is the randomization of $c$.

We denote by $g$ the generator of a prime order group $G$, by ${\sf pk} \in G$ the public key, and by $m\in G$ the plaintext message.

We parse $c$ as $(c_1,c_2)=(g^r,{\sf pk}^r m)$.

To randomize $c$, Bob chooses $s$ at random and computes $c'=(c'_1,c'_2)=(c_1 g^s , c_2 {\sf pk} ^s) = (g^{r+s},{\sf pk}^{r+s} m)$.

To prove that $c'$ is the randomization of $c$, he proves that $\log_g(\frac{c'_1}{c_1}) = \log_{\sf pk}(\frac{c'_2}{c_2})$ using the secret $s$.

Note that this works because $\frac{c'_1}{c_1}=g^s$ and $\frac{c'_2}{c_2}={\sf pk}^s$ have the same discrete logarithm $s$ iff the ciphertext is correctly randomized.


Yes it is possible to use NIZK proof for such cases.

Actually re-randomizing and giving a proof that you have done your computation correctly is one of the necessary steps in NIZK shuffle protocols. In shuffle protocols you get a bunch of ciphertexts $c_1, c_2, \cdots ,c_n$ and shuffle (permute + re-randomize) them and output $c_1', c_2', \cdots ,c_n'$ that should be re-randomized and permuted version of input ciphertexts.

For more details about such proofs, I would recommend to look at NIZK proofs for shuffling that also contains NIZK for re-randomizing ciphertexts. You can find some NIZK shuffle proof in literature such as https://eprint.iacr.org/2017/894 or https://eprint.iacr.org/2016/866.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.