Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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.
