3
$\begingroup$

I was looking at security level offered by KYBER. I have attached the table for the reference. I am little bit confused regarding the security level offered by KYBER.

By definition,

  • Level 1 in the NIST call for proposals (matching or exceeding the brute-force security of AES-128)

  • Level 3 in the NIST call for proposals (matching or exceeding the brute-force security of AES-192)

  • Level 5 in the NIST call for proposals (matching or exceeding the brute-force security of AES-256)

As we can see in the table that Level 1 security offered by Kyber is only 118 (which should be greater than or equal to 128). Moreover Level 3 security offered by Kyber is only 183 which is again less than 192.

What am I missing here?

enter image description here

$\endgroup$

1 Answer 1

4
$\begingroup$

I think you are looking at the wrong metric. You need to look at the number of classical gates (second row from the bottom). NIST in https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf (page 18) estimates that, e.g., for AES-128 an attack requires $2^{143}$ classical gates which is less than the $2^{151.5}$ in the table.

There have been attacks which claim they require less than $2^{143}$ classical gates which would put Kyber-512 under AES-128 but then NIST (I think reasonably) argues that these ignore memory costs and counting them in it is still "harder than AES-128". But the whole thing is a bit messy, see e.g.: https://blog.cr.yp.to/20231125-kyber.html https://blog.cr.yp.to/20231023-clumping.html https://blog.cr.yp.to/20231003-countcorrectly.html (from djb's critique my main takeaway is that NIST "loosened" the requirements and better parameter sets for NTRU could be selected which outperform Kyber).

$\endgroup$
2
  • $\begingroup$ Thanks. One little doubt, where does core-SVP hardness comes into the picture in the NIST evaluation criterion. $\endgroup$ Apr 4 at 14:20
  • $\begingroup$ @VIKASSRIVASTAVA from my understanding. coreSVP is a metric only applicable to lattice-based algorithms (hence the name) but NIST prefers the gate count as it is a generic metric which can be used to compare AES, lattices or codes for examples. IIRC initially the lattice submissions used coreSVP as it was unknown how to convert it to the gate count metric but the latest iterations contain the gate counts as research progressed. You can read more about NIST's conclusions in status reports at csrc.nist.gov/Projects/post-quantum-cryptography/publications $\endgroup$
    – honzaik
    Apr 5 at 9:27

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.