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

  • 1
    $\begingroup$ The Carmichael function $\lambda(p^2)$ would be $=p(p-1)$. $\endgroup$ – gammatester Oct 8 '17 at 22:09
  • $\begingroup$ 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). $\endgroup$ – Mayank Oct 8 '17 at 22:11
  • 2
    $\begingroup$ 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$ $\endgroup$ – gammatester Oct 8 '17 at 22:24
  • 1
    $\begingroup$ But: Even if this technically would work, it is insecure because you can easily get $\lambda $ from $n$. $\endgroup$ – gammatester Oct 8 '17 at 22:28
  • 1
    $\begingroup$ Also, using $p=q$ and $\lambda(pq) = p(p-1)$ only nearly works; non-zero multiples of $p$ do not decipher. $\endgroup$ – 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$.

| improve this answer | |
  • $\begingroup$ 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})$ $\endgroup$ – Mayank Oct 12 '17 at 17:09
  • 1
    $\begingroup$ No. The standard problem that has been studied is one where $p$ and $q$ are independent and random. Anything else is dangerous. $\endgroup$ – Yehuda Lindell Oct 14 '17 at 18:43

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.