2
$\begingroup$

In continuation to this question about length of primes , I am in doubt about the restriction on length of primes itself .

In Paillier cryptosystem , equal length of primes are used .

My doubt is whether this restriction is to ensure the following condition only

$$\gcd(pq,(p-1)(q-1))=1$$

or , there are another security reasons that makes the equal length condition mandate .

I mean, in cryptosystems like RSA, approximately equal length primes are generally preferred for security reasons , If the length is more than specified value, then cryptosystem is not secure.

Is it the same case in paillier cryptosysyem too or not ?

$\endgroup$
4
$\begingroup$

No, exactly equal length of primes $p$ and $q$ is not mandatory for security (or proper functioning) in the Pailler cryptosystem. Sufficient requirements are that $p$ and $q$ are prime, $N=p q$ is hard to factor, and $\gcd(p q,(p-1)(q-1))=1$.

The requirement that $p$ and $q$ are of exactly equal size is usually made in the Pailler cryptosystem because this requirement

  • implies that $p<2q<4p$, which implies $\gcd(p q,(p-1)(q-1))=1$, which is a must for the Pailler cryptosystem to work;
  • is customary in RSA, and thus is an easily met condition, and unobjectionable from a security standpoint;
  • is a consequence of stronger conditions mandated by FIPS 186-4 and the earlier ANSI X9.31 RSA key generation standards, which both require $2^{k-1/2}<p<2^k$ and $2^{k-1/2}<q<2^k$ for integer $k$ at least 512 (and further constrained, including to be a multiple of 64), because it simplifies implementations of RSA, including using the CRT method; and similar implementation considerations apply to the Pailler cryptosystem.

More precisely, on security:

  • even though imposing that $p$ and $q$ are of exactly equal size does reduce the choices for $N$, and thus helps at least some factorization algorithms (notably Fermat's and derivatives), it would be a surprise if such algorithms could be extended to factor with odds $\epsilon$ and expected cost lower than $\epsilon\min(p,q)^u$ operations, where $u\approx2/5$ in our wildest dreams, and even $u\approx1/2$ is hard to reach; thus such algorithms are not to fear in the first place, for they do not have odds worth consideration to factor products of two randomly-generated primes of approximately equal size if that size makes factorization by GNFS hard enough; says $N$ at least 768-bit (the current academic record), thus $\min(p,q)$ at least 350-bit, making $\min(p,q)^{2/5}$ at least 140-bit.
  • on the contrary, that $p$ and $q$ are of exactly equal size slightly increases the expected time to factor $N$ by the sub-exponential ECM for a given size of $N$, and does not lower the expected cost of any other sub-exponential algorithm that we know; thus can be regarded as more beneficial than not from a security standpoint.
$\endgroup$

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.