An injectivity analysis of Crystals-Kyber and Implications on quantum security

The One-Way to Hiding (O2H) Lemma proposed by Bindel et al. (TCC ’19) is a central component of proofs of chosen-ciphertext attack (CCA) security of practical public-key encryption schemes in the Quantum Random Oracle Model (QROM). Recently, Kuchta et al. (EUROCRYPT ’20) introduced a new technique, called measure-rewind-measure, improving upon the O2H lemma. The latter gives a new security reduction that does not suffer from a squared security loss as in Bindel et al. (TCC ’19) but has the number of queries Q as a multiplicative factor. This result is based on an injectivity assumption that requires the probability of two different messages generating the same ciphertext being negligible. The injectivity analysis of concrete schemes was left as an open problem by Kuchta et al. (EUROCRYPT ’20). In this paper, we complement the previous work by investigating the injectivity of a particular scheme in the third round National Institute of Standards and Technology (NIST) Post-Quantum Cryptography (PQC) standardization process. More precisely, we apply the techniques and constructions by Nguyen (ASIACRYPT ’19), along with the approach of calculating decryption error by Bos et al. (EuroS &P ’18), to obtain theoretical and numerical bounds on the injectivity of Crystals-Kyber, which points out a direction of resolving injectivity assumption of concrete scheme in the previous work. Our bounds also give the tightest concrete security guarantees for the QROM CCA security of Crystals-Kyber to date, based on the Module LWE hardness assumption.