2
$\begingroup$

The Paillier CryptoSystem has a public key that $(g,n)$ and the private key which can be exclusive to $\lambda$, where the decryption scheme is:

$m = L(c^\lambda \bmod n^2)/L(g^\lambda \bmod n^2) \bmod n$

Since $1/L(g^\lambda \bmod n^2)$ is fixed and always needed for decryption, it is usually computed once and denoted as $\mu$.

What information does $\mu$ leaks about $\lambda$? Because at the end of the day, even if I have $\mu$, I cannot decrypt. i.e. Can I get $\lambda$ from $\mu$?


A Side Note on the way $\mu$ is constructed, that I think proves the correctness of the assumption:

\begin{align} g &= (1+n)^\alpha \cdot \mathcal{B}^n \pmod{n^2} & & \text{$g$ in the $n^{\text{th}}$ root form} \\ g^\lambda &= (1+n)^{\alpha\lambda} \cdot \mathcal{B}^{n\lambda} \pmod{n^2} & &\text{so base on carmichael's theorem} \\ g^\lambda &= (1+n)^{\alpha\lambda} \pmod{n^2} & & \text{again, based on $n^{\text{th}}$ root rule}\\ g^\lambda &= 1+n\alpha\lambda \pmod{n^2}& & \\ L(g^\lambda) &= \alpha\lambda \pmod{n^2}& &\\ \mu &= 1/\alpha\lambda \pmod{n^2} & \end{align} So, since it is impossible to get $\alpha$ given $g$, the main complexity of the encryption scheme itself, and the last equation is a function of two variable, and there is no way to find either variable.

$\endgroup$
  • $\begingroup$ Could you give your reference? The original paper only replaces $\lambda$ with $\alpha$ on page 10. From the article; Note that this time, the encryption function's trapdoorness relies on the knowledge of $\alpha$ (instead of $\lambda$) as secret key. $\endgroup$ – kelalaka Oct 6 at 21:10
  • $\begingroup$ Aside from the technical details, The question still remains, given $1/L(g^{\alpha} \ mod \ n^2)$, which is fixed, can I get $\alpha$ $\endgroup$ – Walid Ashraf Oct 6 at 21:20
  • 1
    $\begingroup$ Huh? You were asking about $\lambda$ in the question, not $\alpha$, right? $\endgroup$ – Maarten Bodewes Oct 7 at 9:02
  • $\begingroup$ yes, $\lambda$ (The decryption key). $\endgroup$ – Walid Ashraf Oct 7 at 9:15
3
$\begingroup$

What information does $\mu$ leak about $\lambda$?

The safe assumption is: all. It must be assumed that knowledge of $\mu$, together with the public key, allows computing $\lambda$ (which allows decryption and factorization of $n$).

At least, that holds in Paillier's scheme as described in Jonathan Katz and Yehuda Lindell's Introduction to Modern Cryptography (section 13.2.2). In this we have $p$ and $q$ of equal size, $g=n+1$, $\lambda=(p-1)(q-1)$, and $\mu=\lambda^{-1}\bmod n$. It follows that $\lambda=\mu^{-1}\bmod n$, allowing computation of $\lambda$ from $\mu$ and $n$ (using e.g. the extended Euclidean algorithm, which is inexpensive).

While that does not immediately tell how to compute $\lambda$ from $\mu$ and $n$ in Paillier's scheme as in the question, that's enough to show that we can't safely reveal $\mu$.

$\endgroup$
  • $\begingroup$ Ok, but as far as I know, The fast method is using extended Euler's method that needs either $\phi(n)$ or $\lambda(n)$ which are very hard to compute. Based on this the problem remains hard. $\endgroup$ – Walid Ashraf Oct 7 at 18:07
  • $\begingroup$ Another hard way is to use Carmichael's Theorem since $\mu$ is relatively prime with n, $\mu^\lambda = 1\ mod\ n$, which is again not feasible! $\endgroup$ – Walid Ashraf Oct 7 at 18:10
  • $\begingroup$ Hum, it is rather $\mu\,\lambda\equiv1\pmod n$, at least in the variant that I present. $\endgroup$ – fgrieu Oct 7 at 18:49
  • $\begingroup$ Why do you need $\phi(n)$ or $\lambda(n)$ in order to compute the extended Euclidean algorithm on $(\mu, n)$ to find the Bézout coefficients $(\lambda, k)$ satisfying $\lambda \mu + k n = 1$? (Except, of course, insofar as $\lambda$ means $\lambda(n)$ here and revealing $\mu$ is a way to leak $\lambda(n)$.) $\endgroup$ – Squeamish Ossifrage Oct 7 at 19:21
  • $\begingroup$ It was a response to the OP, yes. @WalidAshraf See above. $\endgroup$ – Squeamish Ossifrage Oct 8 at 13:41

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.