0
$\begingroup$

If a system provide n bits of security, it is known that the best possible attack against the system would be 2^n (security parameter). However, why are the key sizes of some cryptosystems much larger than their security parameters? Is it because these cryptosystems have a weak and vulnerable algorithm?

$\endgroup$
2
  • 2
    $\begingroup$ Welcome to Cryptography Could you list some of them by editting into your question? $\endgroup$
    – kelalaka
    Nov 8, 2023 at 22:09
  • $\begingroup$ Consider participating? You earn 2 reputation points for accepting answers from others in case you haven't visited help center. $\endgroup$
    – DannyNiu
    Nov 9, 2023 at 12:58

1 Answer 1

1
$\begingroup$

This can be either a philosophical question or a empirical question, but answer to both these sides can be similar.

First, the title is correct, higher key sizes corresponds to a higher security level. But that's within the same cryptosystem.

Second, public-key cryptosystems are based on mathematical problems, whose solutions admit more efficient cryptanalytic algorithms than brutal-forcing their symmetric-key counterparts:

  • RSA has GNFS,
  • Lattice-based ones have BKZ,
  • Hash-based signatures trades total number of messages that can be signed with signature size.

Elliptic-Curve Discrete Logarithm comes the closest to comparable with symmetric-key crypto, with Pollard's rho giving half the security level against the order of the base point of the elliptic curve group.

Third, even symmetric-key algorithms have hidden costs that people often assume only public-key algorithms have.

For example, the size of the key schedule of a block cipher, the number of rounds of a permutation, the total number of pre-computed constants, etc.

$\endgroup$
1
  • $\begingroup$ nice answer. of course the assumption is that the cryptosystem is correctly implemented and the keys are randomly generated from a uniform distribution or some very close approximation to this $\endgroup$
    – kodlu
    Nov 9, 2023 at 1:29

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.