# Paillier Private $\mu$ and $\lambda$

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.

• 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. – kelalaka Oct 6 '19 at 21:10
• Aside from the technical details, The question still remains, given $1/L(g^{\alpha} \ mod \ n^2)$, which is fixed, can I get $\alpha$ – Walid Hanafy Oct 6 '19 at 21:20
• Huh? You were asking about $\lambda$ in the question, not $\alpha$, right? – Maarten Bodewes Oct 7 '19 at 9:02
• yes, $\lambda$ (The decryption key). – Walid Hanafy Oct 7 '19 at 9:15

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$$.

• 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. – Walid Hanafy Oct 7 '19 at 18:07
• 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! – Walid Hanafy Oct 7 '19 at 18:10
• Hum, it is rather $\mu\,\lambda\equiv1\pmod n$, at least in the variant that I present. – fgrieu Oct 7 '19 at 18:49
• 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)$.) – Squeamish Ossifrage Oct 7 '19 at 19:21
• It was a response to the OP, yes. @WalidAshraf See above. – Squeamish Ossifrage Oct 8 '19 at 13:41