# Paillier's Cryptosystem - Secure Key Size

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);


• @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. – tylo Mar 17 '17 at 10:30
• 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). – Yehuda Lindell Mar 17 '17 at 10:33