Paper 2022/1757
An Injectivity Analysis of CRYSTALS-Kyber and Implications on Quantum Security
Abstract
The One-Way to Hiding (O2H) Lemma is a central component of proofs of chosen-ciphertext attack (CCA) security of practical public-key encryption schemes using variants of the Fujisaki-Okamoto (FO) transform in the Quantum Random Oracle Model (QROM). Recently, Kuchta et al. (EUROCRYPT ’20) introduced a new QROM proof technique, called Measure-Rewind-Measure (MRM), giving an improved variant of the O2H lemma, with a new security reduction that does not suffer from a square-root advantage security loss as in the earlier work of Bindel et al. (TCC ’19).However, the FO transform QROM CCA security reduction based on the improved MRM O2H lemma still requires an injectivity assumption on the underlying CPA-secure determinstic public-key encryption scheme. In particular, the tightness of the concrete security reduction relies on a sufficiently small injectivity bound, and obtaining such bounds for concrete schemes was left as an open problem by Kuchta et al. (EUROCRYPT ’20). In this paper, we address the above problem by deriving concrete bounds on the injectivity of the deterministic CPA-secure variant of CRYSTALS-Kyber, the public-key encryption scheme selected for standardisation by the NIST Post-Quantum Cryptograpy (PQC) standardisation process. We evaluate our bounds numerically for the CRYSTALS-Kyber parameter sets, and show that the effect of injectivity on the tightness of the QROM CCA security of the Fujisaki-Okamoto transformed Kyber KEM is negligible, i.e. allows for a tight QROM CCA security reduction. Consequently, we give tightest QROM CCA security bounds to date for a simplified ‘single hashing’ variant of Kyber CCAKEM against attacks with low quantum circuit depth. Our bounds apply for all the Kyber parameter sets, based on the hardness of the Module Learning with Errors (MLWE) problem.
Note: A preliminary version of this paper has been presented in ACISP 2022. This ex- tended and updated version of the paper contains improved and simplified injectivity bounds and several corrections.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. ACISP 2022
- Keywords
- Post-Quantum CryptographyCRYSTALS-KyberCCA securityQROMOne-Way to HidingInjectivityTight Security
- Contact author(s)
-
xd31412718 @ gmail com
muhammed esgin @ monash edu
amin sakzad @ monash edu
ron steinfeld @ monash edu - History
- 2022-12-27: approved
- 2022-12-22: received
- See all versions
- Short URL
- https://ia.cr/2022/1757
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/1757, author = {Xiaohui Ding and Muhammed F. Esgin and Amin Sakzad and Ron Steinfeld}, title = {An Injectivity Analysis of {CRYSTALS}-Kyber and Implications on Quantum Security}, howpublished = {Cryptology {ePrint} Archive, Paper 2022/1757}, year = {2022}, url = {https://eprint.iacr.org/2022/1757} }