Cryptography
homomorphic-encryption number-theory paillier
Updated Sat, 21 May 2022 16:11:27 GMT

# 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

## Solution

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

• +0 – 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})$ — Oct 12, 2017 at 17:09
• +1 – No. The standard problem that has been studied is one where $p$ and $q$ are independent and random. Anything else is dangerous. — Oct 14, 2017 at 18:43

External links referenced by this document: