# How to prove correct decryption in Paillier cryptosystem

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.

• Yehuda Lindell's answer does not appear to answer the original question. Damgard and Jurik's solution (as described in 5.2) requires knowledge of the randomness used to encrypt the ciphertext $c$. In the case they originally consider this is not an issue. However, in the op's case, Alice does not know the randomness. Nor can she efficiently compute it. In short, Alice cannot convince Bob using the method of Damgard and Jurik in 5.2. I do not know of any solution which fits the requirements. – hainest Feb 13 '18 at 12:07
• @hainest "Nor can she efficiently compute it."; actually, as the holder of the private key, she can. If she has the private key, then given $r^n \bmod n^2$, she can compute the $n$-th root, recovering $r$ (by computing the $n$-th root of $r^n \bmod p^2$ and $r^n \bmod q^2$, and gluing the two back together using CRT. – poncho Feb 13 '18 at 19:18
• @hainest Damgard and Jurik gave in their article an afficient algorithm for computing randomness (see Theorem 1). – Alexey Ustinov Mar 14 '18 at 8:08

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:

1. Bob computes $R = C \bmod N$ and sends $R$ to Alice;
2. Alice using her private key computes $r' = R^{N^{-1} \bmod \lambda} \bmod N$ and sends $r'$ to Bob;
3. 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$.

1. Bob computes $R = C \bmod N$ and sends $R$ to Alice;
2. Alice using her private key computes $r'' = R^d\bmod N$ and sends $r''$ to Bob;
3. 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}$.