1
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ Okay I solved it lol $\endgroup$
    – Bella
    Oct 30 '20 at 2:33
  • 1
    $\begingroup$ 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? $\endgroup$
    – fgrieu
    Oct 30 '20 at 8:55
  • 1
    $\begingroup$ @fgrieu I will answer my own question $\endgroup$
    – Bella
    Nov 1 '20 at 2:37
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.