# Prove the correctness of decryption process of Paillier cipher

The definition of Paillier cryptosystem is the same as the one on wikipedia.

Now the random integer $$g$$ is chosen of the form $$g=(1+n)^{\alpha}\beta^{n}\bmod n$$, where $$\alpha$$ and $$\beta$$ are in $$\mathbb{Z}_{n}^{*}$$. Prove that $$m\;=\;L(c^{\lambda}\bmod n^{2})\mu\bmod n\;=\;\frac{L(c^{\lambda})\bmod n^{2}}{L(g^{\lambda})\bmod n^{2}}\bmod n$$, where $$L(x)=\displaystyle\left\lfloor\frac{x-1}{n}\right\rfloor$$ denotes the quotient when $$x-1$$ is divided by $$n$$ and $$\mu=\left(L\left(g^{\lambda}\bmod n^{2}\right)\right)^{-1}\bmod n$$.

(Carmichael's theorem: For any $$r\in \mathbb{Z}_{n^{2}}^{*}$$, we have $$r^{n\lambda}\equiv1\bmod n^{2}$$.)

The above is the question description. The following is what I came up with.

\begin{align*} L(c^{\lambda}\bmod n^{2}) &= \frac{c^{\lambda}\bmod n^{2}-1}{n} \\ &= \frac{g^{m\lambda}r^{n\lambda}\bmod n^{2}-1}{n} \\ &= \frac{(g^{m\lambda}-1)r^{n\lambda}\bmod n^{2}}{n} \\ &= \frac{g^{m\lambda}-1 \bmod n^{2}}{n} \end{align*} \begin{align*} L(g^{\lambda}\bmod n^{2}) &= \frac{g^{\lambda}\bmod n^{2}-1}{n} \\ &= \frac{g^{\lambda}-1 \bmod n^{2}}{n} \end{align*}

But I have no idea how to proceed. I still haven't used the formula for $$g$$. I think the solution may involve some finite field theorems but I really cannot recall any.

• Okay I solved it lol Oct 30 '20 at 2:33
• Dear Bella, among options: you can make an answer, or delete the question. Either would solve my problem as a moderator: what to do with this?
– fgrieu
Oct 30 '20 at 8:55
• @fgrieu I will answer my own question Nov 1 '20 at 2:37

First, we simplify $$\mu$$. \begin{align*} g &= (1+n)^{\alpha}\beta^{n} \bmod n^{2} \\ g^{\lambda} &= (1+n)^{\alpha\lambda}\beta^{n\lambda}\bmod n \\ &= (1+n)^{\alpha\lambda}\bmod n^{2} \\ &= (1+n\alpha\lambda)\bmod n^{2} \\ L(g^{\lambda}\bmod n^{2}) &= (\alpha\lambda)\bmod n^{2} \end{align*} Then, let's take a look at $$L(c^{\lambda}\bmod n^{2})$$. \begin{align*} c &= g^{m}r^{n}\bmod n^{2} \\ c^{\lambda} &= g^{m\lambda}r^{n\lambda}\bmod n^{2} \\ &= g^{m\lambda}\bmod n^{2} \\ &= (1+n\alpha\lambda)^{m}\bmod n^{2} \\ &= (1+mn\alpha\lambda)\bmod n^{2} \\ L(c^{\lambda}\bmod n^{2}) &= (m\alpha\lambda)\bmod n^{2} \end{align*}
Hence, $$\frac{L(c^{\lambda}\bmod n^{2})}{L(g^{\lambda}\bmod n^{2})}=m\bmod n$$, the decryption process of Paillier cipher is correct.