Score:2

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

us flag

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.

Score:1
ru flag

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.

Manglemix avatar
us flag
Thank you this is a very comprehensive answer
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.