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
Bob sends a ciphertext obtained by Paillier encryption to Alice.
Alice has the private key. She decrypts the ciphertext and returns the plaintext to Bob.
How can Alice convince Bob that the plaintext is correct to this ciphertext? Bob only has the encrypted plaintext and the public key of this encryption.
This can be done by using a zero-knowledge proof to prove that a Paillier ciphertext is an encryption of zero. Specifically, let $c$ be the original ciphertext, and let $m$ be the decryption that Alice sends back to Bob. Then, both Alice and Bob can each locally use the homomorphic property to compute a ciphertext $c'$ that is an encryption of the value encrypted in $c$ minus $m$. Note that if $c$ is an encryption of $m$, then $c'$ is an encryption of zero.
Thus, all that is needed is for Alice to prove in zero-knowledge that $c'$ is an encryption of zero (equivalently, that $c'$ is a $n^2$'d power). This can be done very efficiently, using the method described in Section 5.2 of A Generalization of Paillier’s Public-Key System with Applications to Electronic Voting by Damgard and Jurik.
In light of a comment in a different answer, it is possible for the prover to compute the randomness given the public key, if it doesn't have it. Specifically, let $c=r^N \bmod N^2$ (this is an encryption of zero). Then, compute $M= N^{-1} \bmod \phi(N)$ and $r = c^M \bmod N$. This works since $c^M = r^{N\cdot M} = r^{1+k\cdot \phi(N)} = r \bmod N$.
Here is an alternate, easier way.
Fix the notation. Let $N = pq$ for two large primes $p$ and $q$. Alice 's public key is $N$ while her private key is $\lambda = \operatorname{lcm}(p-1,q-1)$.
The message space is $\mathcal{M} = \mathbb{Z}_N$. The encryption of a message $m \in \mathcal{M}$ is given by $C = (1+mN)r^N \bmod N^2$ for some random integer $r \in [1, N)$.
To get the decryption of a ciphertext $C$ in a verifiable way, Bob engages in the following protocol with Alice:
- Bob computes $R = C \bmod N$ and sends $R$ to Alice;
- Alice using her private key computes $r' = R^{N^{-1} \bmod \lambda} \bmod N$ and sends $r'$ to Bob;
- Bob checks that $(r')^N \equiv R \pmod N$. If so, Bob recovers plaintext $m$ as $m= \frac{C\cdot (r')^{-N} -1 \bmod N^2}{N}$. Otherwise, Alice cheated.
This presents the further advantage that plaintext $m$ is unknown to Alice. Moreover, the bandwidth requirements are minimal: Alice and Bob only exchange $2\log_2 N$ bits ($R$ and $r'$).
Computations can be slightly sped up. Here is a variant. Alice defines her private key as $d = -N^{-1} \bmod \lambda$.
- Bob computes $R = C \bmod N$ and sends $R$ to Alice;
- Alice using her private key computes $r'' = R^d\bmod N$ and sends $r''$ to Bob;
- Bob computes $S = (r'')^N \bmod N^2$ and checks that $S \cdot R\equiv 1 \pmod N$. If so, Bob recovers plaintext $m$ as $m= \frac{C\cdot S -1 \bmod N^2}{N}$. Otherwise, Alice cheated.
The correctness follows from the next proposition.
Proposition. For any $r \in \mathbb{Z}_{N^2}$, one has $r^N \equiv (r\bmod N)^N \pmod {N^2}$.
Proof. Write $r = r_0+ r_1N$ where $r_0 = r \bmod N$ and $r_1 = \lfloor r/N\rfloor$. The binomial formula yields $$r^N=(r_0 + r_1N)^N \begin{array}[t]{l}= \displaystyle\sum_{k=0}^N {N \choose k} r_0^{N-k} (r_1N)^k\\ = r_0^N + Nr_0^{N-1}(r_1N) + N(N-1)r_0^{N-2}(r_1N)^2 + \dots\end{array}$$ Hence, reducing modulo $N^2$, we obtain $r^N \equiv r_0^N \equiv (r\bmod N)^N\pmod {N^2}$.
