1
$\begingroup$

How do we measure the security levels of Post Quantum Cryptographic algorithms such as: NTRU Prime, Saber, Kyber,...that are submited to NIST PQC Standardization Process(Competition) in general?

I read the documentation in the NIST submission package of NTRU Prime but understanding the security levels does seem very complicated for the PQC algorithms unlike the non-PQC ones for which we can ise easy comparison methods to AES-256. They talk about transforms and CCA, CPA security levels depending on some parameters but it seems complicated to me.

Can someone explain the security measurement for PQC algorithms in general?

$\endgroup$
1
  • $\begingroup$ Huh? NIST did specify target security levels in bits, right? This is why the candidates provide multiple "classes" of their algorithm. In general the target security levels are 128 bit, 192 bit and 256 bit (comparable to AES key sizes), just like classical algorithms but now secure against quantum analysis. If the algorithms score lower than that they are considered broken (to a certain extend). $\endgroup$
    – Maarten Bodewes
    Jan 20, 2022 at 10:51

2 Answers 2

2
$\begingroup$

This question is related. Note that this question does say that security is analyzed by comparison with AES/SHA3, as you suspect.

Perhaps the most informative way to learn more about this is to go "hands on" though, and read the security analysis sections of various NIST PQC round 3 candidates. These should be close to the community consensus of how to analyze the schemes (although there are still disagreements, which are usually discussed on the NIST PQC google group). Examples of a few of the disagreements are things like:

  • Does rounding (for compression purposes) improve the security of lattice-based KEMs? If so, by how many bits? (or by what "CoreSVP count", a metric specific to the analysis of lattice-based schemes)
  • What does "CoreSVP" count mean precisely?
  • How accurate are estimates (from the cryptanalysis of "noisy" lattice-based primitives) when applied to lattice-based primitives with solely "deterministic" noise (induced from rounding)?
  • How to deal with appropriately analyzing the memory costs of attacks. A big deal here is the differences between quantum memory (meaning qubits needed) and quantum-accessible classical memory, which should be much more abundant (for example, $2^{30}$ classical memory is currently quite feasible, but I have never heard of a confident estimate of when we should expect $2^{30}$ logical qubits --- I don't believe we've even hit one logical qubit yet!).
  • How to appropriately handle non-tight reductions? Often QROM reductions are less tight than ROM reductions. Should parameters be set looser to compensate, or is this an artifact of the relatively new model?

In general though, up to some disagreements, the security measurements are roughly similar to what they are for classical security (meaning via comparisons to the security of AES/SHA3), and can be found within the various submissions' specifications. If you read enough of them, you should get a pretty good idea of how the community has (mostly) settled on analyzing the security of various schemes.

You can read the google group as well of course, but it is a lot more... free form than the submissions, so is perhaps not the most succinct source of information. It is worth mentioning that it can be entertaining to read regardless, as the debate can get somewhat animated (which perhaps contributes to it being less information dense than the submissions).

$\endgroup$
1
  • 1
    $\begingroup$ "debate can get somewhat animated" Bernstein vs Peikert, round 247, fight! $\endgroup$ Jan 23, 2022 at 20:07
1
$\begingroup$

Often times, (asymmetric) encryption schemes can be discussed in terms of provable security - we can show that the scheme is secure under certain attacks if the underlying cryptographic primative is hard. In other words, provable security relies on reducing our problem to its primative, for example, the RSA problem is reducable to the factoring problem.

Generally, the following four properties are discussed, IND, CPA, CCA, and CCA2:

IND (indistinguishibility): An adversary cannot distinguish the encryption of any two messages of the same length ie. if given a challenge cipher text $c$, they cannot tell if $c$ came from $m_1$ or $m_2$.

IND-CPA (indistinguishibility under a chosen plaintext attack): An adversary cannot distinguish which message was used to create a challenge ciphertext if given access to the public key (in other words, they are able to create ciphertexts from chosen messages).

IND-CCA (indistinguishibility under a chosen ciphertext attack): The same set up as before, however this time, the adversary has a decryption oracle they are able to query until they are given the challenge ciphertext.

IND-CCA2 (indistinguishibility under an adaptive chosen ciphertext attack): Like the previous example, however now the adversary is allowed to query the decryption oracle even after recieving the challenge (with the caveat they are not allowed to enter the challenge ciphertext to the oracle)

These are chosen to be discussed as if we can prove that (assuming the proof applied in the proper context), we only need worry about the hardness of the problem underlying it.

The definitions of these properties may be slightly different for symmetric schemes (they are not based on mathematical problems), but we are able to prove analogous results, again under certain conditions (think key length).

This allows us to now assess the 'security level' for these parameters in a way that can be translated and compared to that of AES.

$\endgroup$

Your Answer

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