2
$\begingroup$

Given Paillier's Cryptosystem. What size in bits would be considered secure for now and the near future? I know it differs for every cryptosystem.

For reference, the most important part of my implementation of the key generation is given below. I would wish like to increase the performance of my app but remain secure for the near future. What would be the recommended bit size, and why? Thank you for your time.

final int PRIME_CERTAINTY = 100;
final int BITLENGTH = ???;
BigInteger p, q;
do {
  p = BigInteger.probablePrime(BITLENGTH / 2, new SecureRandom());
} while (!p.isProbablePrime(PRIME_CERTAINTY));

do {
  q = BigInteger.probablePrime(BITLENGTH / 2, new SecureRandom());
} while (!q.isProbablePrime(PRIME_CERTAINTY) || q.equals(p));

n = p.multiply(q);
$\endgroup$
2
$\begingroup$

You should be using a 2048-bit modulus, as with RSA. Personally I feel comfortable with 1536, but 2048 is considered the minimum standard.

$\endgroup$
  • $\begingroup$ Does this imply that n should be at least 2048 bits? $\endgroup$ – BARJ Mar 17 '17 at 10:12
  • 1
    $\begingroup$ @BARJ Yes, $n$ should have 2048 bits. If you have $|n^2| = 2048$, this is considered too short today. See the latest recommendation on keylength.com, a factoring modulus should have minimum length $2000$ - regardless of the potency of $n$ you actually use in a construction. $\endgroup$ – tylo Mar 17 '17 at 10:30
  • 1
    $\begingroup$ If you can factor $n$ then it's broken. So, $n$ must be of length 2048, making the operations mod $n^2$ of length 4096. So, indeed this is not very efficient (but that's life). $\endgroup$ – Yehuda Lindell Mar 17 '17 at 10:33

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.