2
$\begingroup$

Here (https://www.safecrypto.eu/pqclounge/round-2-candidates/) are collected all the proposals which passed the first round of NIST Post-Quantum Cryptography Standardisation process. What does the abbreviations in "NIST security categories" column mean? Where can I find a formal definition of them?

$\endgroup$
  • 3
    $\begingroup$ Did you execute a little search? see here at page 16. $\endgroup$ – kelalaka Mar 4 at 21:31
5
$\begingroup$

A copy and paste from page 16 of NIST document Submission Requirements and Evaluation Criteria for the Post-Quantum Cryptography Standardization Process;

  1. Any attack that breaks the relevant security definition must require computational resources comparable to or greater than those required for key search on a block cipher with a 128-bit key (e.g. AES128)
  2. Any attack that breaks the relevant security definition must require computational resources comparable to or greater than those required for collision search on a 256-bit hash function (e.g. SHA256/ SHA3-256)
  3. Any attack that breaks the relevant security definition must require computational resources comparable to or greater than those required for key search on a block cipher with a 192-bit key (e.g. AES192)
  4. Any attack that breaks the relevant security definition must require computational resources comparable to or greater than those required for collision search on a 384-bit hash function (e.g. SHA384/ SHA3-384)
  5. Any attack that breaks the relevant security definition must require computational resources comparable to or greater than those required for key search on a block cipher with a 256-bit key (e.g. AES 256)
$\endgroup$
  • 3
    $\begingroup$ Unfortunately, the computational resources required to break any of the five listed problems in the Quantum realm isn't nearly as easy to define as it is in the classical realm... $\endgroup$ – poncho Mar 5 at 20:08
  • $\begingroup$ @poncho The document goes into more detail about that, giving information on the quantum gate depth and how e.g. Grover's algorithm will likely be implemented as a number of parallel processes each with a short lifetime in order to deal with quantum decoherence. Of course, that also means that a significant performance hit to Grover's algorithm since it is not easy to parallelize efficiently. $\endgroup$ – forest Mar 6 at 6:31
  • 1
    $\begingroup$ @forest: which is largely my point. On a classical computing, breaking AES-128 with probability 0.5 will take $2^{127}$ AES evaluations, end of story. On a quantum computer, the effort to break AES-128 with probability 0.5 will depend, among other things, the value of MAXDEPTH you assume (the NIST doc does not mandate a specific value), and the circuit depth of a quantum AES circuit (and the Grassl et al value is probably not the best you can do) $\endgroup$ – poncho Mar 6 at 13:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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