Paper 2022/212
Tight Analysis of Decrypton Failure Probability of Kyber in Reality
Boyue Fang, Weize Wang, and Yunlei Zhao
Abstract
Kyber is a candidate in the third round of the National Institute of Standards and Technology (NIST) PostQuantum Cryptography (PQC) Standardization. However, because of the protocol's independence assumption, the bound on the decapsulation failure probability resulting from the original analysis is not tight. In this work, we give a rigorous mathematical analysis of the actual failure probability calculation, and provides the Kyber security estimation in reality rather than only in a statistical sense. Our analysis does not make independency assumptions on errors, and is with respect to concrete public keys in reality. Through sample test and experiments, we also illustrate the difference between the actual failure probability and the result given in the proposal of Kyber. The experiments show that, for Kyber512 and 768, the failure probability resulting from the original paper is relatively conservative, but for Kyber1024, the failure probability of some public keys is worse than claimed. This failure probability calculation for concrete public keys can also guide the selection of public keys in the actual application scenarios. What's more, we measure the gap between the upper bound of the failure probability and the actual failure probability, then give a tight estimate. Our work can also reevaluate the traditional $1\delta$ correctness in the literature, which will help reevaluate some candidates' security in NIST postquantum cryptographic standardization.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Preprint. MINOR revision.
 Keywords
 PostQuantum CryptographyLearning with ErrorsKey Encapsulation MechanismDecryption Failure
 Contact author(s)
 byfang16 @ fudan edu cn
 History
 20220225: received
 Short URL
 https://ia.cr/2022/212
 License

CC BY
BibTeX
@misc{cryptoeprint:2022/212, author = {Boyue Fang and Weize Wang and Yunlei Zhao}, title = {Tight Analysis of Decrypton Failure Probability of Kyber in Reality}, howpublished = {Cryptology ePrint Archive, Paper 2022/212}, year = {2022}, note = {\url{https://eprint.iacr.org/2022/212}}, url = {https://eprint.iacr.org/2022/212} }