Is this a safe zero knowledge proof that two paillier encryptions are equal?

Question

We have encryptions $c_1$ and $c_2$, the person who knows the plaintext and randomness in both wants to prove that they know it. Let $r_1$ and $r_2$ be the randomness values in $c_1$ and $c_2$ respectively. The prover then randomly generates another random number, $z$. They then calculate $a_1 = r_1^n z^n$, $a_2 = r_2^n z^n$. These are the proofs. A verifier would just have to multiply $a_2$ with $c_1$ and $a_1$ with $c_2$ and check if the products are equal. If they are, then it should be safe to assume that $c_1$ and $c_2$ contain the same secret. If $a_1$ is $c_2$ and $a_2$ is $c_1$ then the proof is obviously false despite the equality being true.

Answer 1

This is very unsafe. Anyone can produce a fake proof that two ciphertexts are equivalent.

Given $c_1$ and $c_2$, choose a random $x$ and let $a_1=c_1x\mod {n^2}$ and $a_2=c_2x\mod {n^2}$. We see that $a_1c_2\equiv a_2c_1\pmod {n^2}$ which matches the verification criterion.

A proof that $c_1$ and $c_2$ are encryptions of the same value is equivalent to showing that $c_1/c_2\pmod{n^2}$ is an $n$th power. Here's a sigma protocol for that proof that you can make non-interactive with the usual Fiat-Shamir schtick.

To prove that $k$ is an $n$th power modulo $n^2$

We assume that the prover is endowed with $s:k\equiv s^n\pmod{n^2}$.

Commitment

The prover generates a uniform random number $r\mod{n^2}$, calculates $c=r^n\mod{n^2}$ and publishes $c$.

Challenge

The verifier requests that prover publish either $r$ such that $r^n=c\mod{n^2}$ or $r'$ such that $r'^n=ck\mod{n^2}$.

Response

Prover publishes either $r$ or $r'=rs\mod{n^2}$ according to the challenge.

If both possible responses are available to a responder then responder would know $s=r'/r$ so that knowledge of both responses proves knowledge of $s$. Therefore the protocol is correct with high probability as the number of protocol iterations increases.

Verifer could generate random protocol transcripts for themselves by first picking the challenge, then the response, then the commitment. Therefore the protocol is zero-knowledge.