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}) &amp;= \frac{c^{\lambda}\bmod n^{2}-1}{n} \\
&amp;= \frac{g^{m\lambda}r^{n\lambda}\bmod n^{2}-1}{n} \\ &amp;= \frac{(g^{m\lambda}-1)r^{n\lambda}\bmod n^{2}}{n} \\ &amp;= \frac{g^{m\lambda}-1 \bmod n^{2}}{n}
\end{align*}
\begin{align*}
L(g^{\lambda}\bmod n^{2}) &amp;= \frac{g^{\lambda}\bmod n^{2}-1}{n} \\
&amp;= \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.
First, we simplify $\mu$.
\begin{align*}
    g &amp;= (1+n)^{\alpha}\beta^{n} \bmod n^{2} \\
    g^{\lambda} &amp;= (1+n)^{\alpha\lambda}\beta^{n\lambda}\bmod n \\
    &amp;= (1+n)^{\alpha\lambda}\bmod n^{2} \\
    &amp;= (1+n\alpha\lambda)\bmod n^{2} \\
    L(g^{\lambda}\bmod n^{2}) &amp;= (\alpha\lambda)\bmod n^{2}
\end{align*}
Then, let's take a look at $L(c^{\lambda}\bmod n^{2})$.
\begin{align*}
    c &amp;= g^{m}r^{n}\bmod n^{2} \\
    c^{\lambda} &amp;= g^{m\lambda}r^{n\lambda}\bmod n^{2} \\
    &amp;= g^{m\lambda}\bmod n^{2} \\
    &amp;= (1+n\alpha\lambda)^{m}\bmod n^{2} \\
    &amp;= (1+mn\alpha\lambda)\bmod n^{2} \\
    L(c^{\lambda}\bmod n^{2}) &amp;= (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.