4
$\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);
Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Does this imply that n should be at least 2048 bits? $\endgroup$
    – BARJ
    Commented Mar 17, 2017 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
    Commented Mar 17, 2017 at 10:30
  • 2
    $\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
    Commented Mar 17, 2017 at 10:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.