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$
4
  • $\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, 2019 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$ Oct 6, 2019 at 21:20
  • 1
    $\begingroup$ Huh? You were asking about $\lambda$ in the question, not $\alpha$, right? $\endgroup$
    – Maarten Bodewes
    Oct 7, 2019 at 9:02
  • $\begingroup$ yes, $\lambda$ (The decryption key). $\endgroup$ Oct 7, 2019 at 9:15

1 Answer 1

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$
7
  • $\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$ Oct 7, 2019 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$ Oct 7, 2019 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, 2019 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$ Oct 7, 2019 at 19:21
  • $\begingroup$ It was a response to the OP, yes. @WalidAshraf See above. $\endgroup$ Oct 8, 2019 at 13:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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