# Taking $p$ and $q$ to be the same value in paillier cryptosystem

I was implementing Paillier cryptosystem when I came across the fact that as soon as I take the primes $p$ = $q$, I start getting incorrect decryption results.
As far as I can understand, when I take $p$ = $q$, the function $L(x)$ returns a fractional value instead of an integer one, meaning that in case when the primes are equal $L($$g^{\lambda}$ mod $n^{2}$) is not an integer. I also get that when the primes are equal, then $\lambda = (p-1)$, since lcm of $(a, a)$ is $a$.
Can someone explain that where do things go wrong when the primes are equal?
Reference for the scheme

• The Carmichael function $\lambda(p^2)$ would be $=p(p-1)$. – gammatester Oct 8 '17 at 22:09
• Yeah, I know that but what if I don't take $\lambda$ as $\phi(n)$. I can take $\lambda = lcm(p-1, q-1) = p-1$ (in this case). – Mayank Oct 8 '17 at 22:11
• No, I mean the Carmichael function which is $\lambda(pq)=(p-1)(q-1)$ for different odd primes $p,q$. And if you take $p=q$ you should try $\lambda = p(p-1)$ where you get at least $g^\lambda-1\equiv 0 \bmod n$ – gammatester Oct 8 '17 at 22:24
• But: Even if this technically would work, it is insecure because you can easily get $\lambda$ from $n$. – gammatester Oct 8 '17 at 22:28
• Also, using $p=q$ and $\lambda(pq) = p(p-1)$ only nearly works; non-zero multiples of $p$ do not decipher. – fgrieu Oct 9 '17 at 5:30

Irrespective of the math, you CANNOT take $p=q$ since in this case the scheme is completely insecure. You must choose random, independent primes $p$ and $q$.
• Am I correct in saying that unless I take the difference of |$p-q$| to be > than the limits of brute attacks, I can consider the implementation to be safe. Though, I am not considering NFS attacks here. I think that they might also come into play and as far as I remember, using meet-in-the-middle algorithms like baby-step-giant-step, we should take this difference to be more, since such algorithms solve integer factorization in close to $O(n^{1/4})$ – Mayank Oct 12 '17 at 17:09
• No. The standard problem that has been studied is one where $p$ and $q$ are independent and random. Anything else is dangerous. – Yehuda Lindell Oct 14 '17 at 18:43