# NIZK proof for cipher randomisation

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.