Join Log in
Score:3
avatar Crypto

How to calculate the n in n-bit security of a crypto algorithm?

ng flag
ystark

I think I'm likely missing the term because searching for this is coming up with not so precise results. I'm looking to calculate the n-bit security of say Paillier vs ElGamal vs EC ElGamal, when I use an x-bit key.

This paper states that "in order to achieve the 128-bit security level, 4096-bit p and 256-bit q are normally used in ElGamal, while in Paillier, the size of n is normally chosen to be 4096 bits."

How can I calculate what values are required for 256-bit security? Is it simply multiplied by two here?

221
3 + 0
Score:5
ckamath avatar Crypto
ag flag
ckamath

TLDR: The size of the group/ring is dictated by the fastest currently-known attack (as explained in this Wikipedia article).

Details. For the case of discrete-log in $\mathbb{Z}_p^*$ and factoring $\mathbb{Z}_N^*$, the fastest currently-known algorithm is the general number field sieve (GNFS). GNFS has a run-time of (roughly) $L_n(1/3,2)$, where $$L_n(\alpha,c):=e^{(c+o_n(1))n^\alpha\ln^{1-\alpha}(n)}$$ is the $L$-notation and $n$ denotes the bit-length of (the standard representation of) $p$ or $N$ (i.e., $\lceil(\log(p)\rceil$ and $\lceil(\log(N)\rceil$, respectively).$^*$ Since $b$-bit security for a scheme means that it should take any algorithm $2^b$ operations to break it, to compute the $n$ for $\mathbb{Z}_p^*$ and $\mathbb{Z}_N^*$ that achieves $128$-bit security one has to solve for $$2^{128}\approx e^{2n^{1/3}\ln^{2/3}(n)}\Leftrightarrow n\ln^2(n)\approx64^3.$$ This will give an ball-park figure of what the size of the modulus should be -- as computed in this answer this turns out to be around $3072$ bits (or $4096$ bits to be on the safer side?). Since we do not know any better means to solve DDH/CDH (the problems that underlie El-Gamal-type schemes) than to compute discrete logs, El-Gamal in (quotiented) $\mathbb{Z}_p^*$ needs to be deployed with primes of size $\approx3072/4096$ bits.

Similarly, since we do not know any better means to solve the decision quadratic residuosity problem in $\mathbb{Z}_{N^2}^*$ (the problem that underlies Paillier's cryposystem) than to factor $N$, by the same argument above, we need to work $N$ of size $\approx 3072/4096$ bits.

For discrete-log in elliptic curves, I believe we do not know anything better than generic discrete-log algorithms (e.g., Pollard's rho) which run in time square-root the size of the group. Therefore, for $128$-bit security of EC-El-Gamal, it suffices to work with elliptic curves over a field of size $2^{256}$. (This also means that EC-El-Gamal is significantly more communication-efficient than El-Gamal in $\mathbb{Z}_p^*$.)

$^*$The original GNFS is a heuristic. But as pointed out by @djao (see this comment), there are provable variants which run in $\approx L_n(1/3,3)$.

0 + 2
djao avatar
cn flag
djao
The number field sieve has been proven to run in the claimed time, and in particular is (provably) faster than the quadratic sieve. https://cstheory.stackexchange.com/questions/32508/
2
Reply
ckamath avatar
ag flag
ckamath
Thanks! I wasn't aware. Will update the answer.
0
Reply
Score:1
TurkBitig avatar Crypto
fr flag
TurkBitig

Each algorithm's n-bit security is calculated via "best attack method". For example RSA is based on factorization problem and it can be solved with "Number Field Sieve" algorithm, so we use NFS's "calculation complexity" to determine RSA's n-bit security level. For cryptographic hash functions we use "birthday attack" to calculate n-bit security etc.

0 + 0
Score:0
SAI Peregrinus avatar Crypto
si flag
SAI Peregrinus

There's no single, simple answer. n-bit security means the base 2 logarithm (usually written just $\log$) of the number of "operations" needed to break the primitive.

For a symmetric cipher like AES-128, an "operation" is usually a trial encryption or decryption, far more than a single CPU cycle. AES-128 generally has 128-bit security because there are $2^{128}$ possible keys, and there's no general attack faster than trying all the keys, and $\log(2^{128})=128$.

Asymmetric systems like Paillier, ElGamal, and EC ElGamal all have attacks much faster than trying all possible keys. So to calculate the "equivalent symmetric security" in bits you need to calculate the cost of the best known attack against the parameters used.

You also need to decide whether the cost of an "operation" in such an attack is dramatically different from an "operation" attacking the symmetric cipher(s) you're comparing to, and if so scale your number of operations appropriately. That last consideration is why asymmetric systems like ElGamal would have half as many bits of security against attack by general-purpose error-corrected quantum computers as they do against current computers.

I'm not particularly familiar with the state-of-the-art in attacks against the three systems in question, so I can't give absolute numbers. This is thus only a partial answer to the question asked.

0 + 0
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.