Cracking an ideal block cipher is basically a brute force key enumeration. The complexity of the attack is exponential, growing as $2^b$. Cracking ECC is also exponential, but the cost grows as $2^{\frac{b}{2}}$ where $b$ is the public-key size (with a compact representation).

I ask whether there is a class of asymmetric cipher algorithms that can make the best (known) attack cost grow faster with public-key size $b$ than in ECC. Or if on the contrary, it it possible to prove that no asymmetric cipher can have complexity growing faster than in ECC.

  • $\begingroup$ keylength.com $\endgroup$
    – kelalaka
    Nov 27, 2023 at 14:29
  • $\begingroup$ Since there are two keys, we must specify the size of which key we are considering [update: done]. It's easy to shorten the private key to $b$-bit of even slightly less, not so for the public key, thus I guess this should be the size considered. I thought we have a question like can we have asymmetric cryptography with less than $2b$-bit public key? but I fail to locate it. $\endgroup$
    – fgrieu
    Nov 27, 2023 at 15:25
  • $\begingroup$ Thanks for your reply, my English is not very good, I used the translation software, maybe the translation of professional terms is not very good. $\endgroup$
    – 槿铃兔
    Nov 27, 2023 at 15:36
  • $\begingroup$ The question you raise is important and I did lose sight of whether I was referring to the public or private key. However, through the security comparison table of RSA and ECC indicated on the network, I guess it should be comparing the length of RSA's public key with the length of ECC's private key, because when considering RSA, we consider the factorization of n (and n is the public key of RSA), and when considering ECC, we consider the discrete logarithm of the public key (but the answer range is under the max value the private key can be set). $\endgroup$
    – 槿铃兔
    Nov 27, 2023 at 15:38
  • 1
    $\begingroup$ I edited the question. Mostly I replaced "two-key encryption" by "asymmetric cipher", and stated that we consider the bit size $b$ of public key in a compact form (e.g. with point compression in ECC). Notice that asymmetric cryptography includes signature, key exchange, and asymmetric cipher; but the question only is about the later (as was the original). $\endgroup$
    – fgrieu
    Nov 27, 2023 at 16:30


Your Answer

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

Browse other questions tagged or ask your own question.