Paper 2022/1757

An Injectivity Analysis of CRYSTALS-Kyber and Implications on Quantum Security

Xiaohui Ding, Monash University
Muhammed F. Esgin, Monash University, CSIRO's Data61
Amin Sakzad, Monash University
Ron Steinfeld, Monash University
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)
PDF
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.