Confusion in the security level offered by KYBER

Question

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?

Answer 1

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).