Anonymity of NIST PQC Round 3 KEMs

Mihir Bellare Y, Hannah Davis, Felix Günther

Hecht, Pedro

Muhamad Akrom, Supriadi Rustad, Guruh Fajar Shidik +3 more

JiaYv An, Yankun Gao, Lei Han

Driven by advances in the standardization of NIST’s Post-Quantum Cryptography (PQC) algorithms, research on constructing Password Authenticated Key Exchange (PAKE) protocols using Key Encapsulation Mechanisms (KEMs) has gained considerable attention. Several PAKE protocols have established precise security requirements for the underlying KEM. Arriaga et al. introduced a PAKE protocol called CHIC, which requires the KEM to achieve anonymity under plaintext-checkable attacks (ANO-1PCA). An anonymous KEM does not leak any information about which public key was used for encryption. It protects the identities and privacy of participants and is critical in preventing identity-guessing attacks, therefore, anonymity is also called key-privacy. The anonymity of NIST PQC Round-3 candidates has recently been analyzed, some of which satisfied ANO-CCA.Huguenin-Dumittan and Vaudenay proposed two efficient constructions, TCHand TH, to create KEM from public-key encryption (PKE) schemes. Jiang et al. introduced TRHbased on TH. These constructions can transform any OW-CPA PKE into an IND-qCCA KEM efficiently and avoid re-encryption. However, prior to this work, no research has been conducted to determine whether these constructions preserve or lift anonymity.In this paper, we proved that for any OW-CPA, DS-IND PKE, the construction KEMRH= TRH[PKE,H] achieves ANO1-CCA in the quantum random oracle model (QROM). We then construct a KEM called KyberRH, and provide an algorithm for the CHIC protocol using KyberRH.

Donghoon Lee, Eun-Young Seo, Young-Sik Kim +1 more

In this paper, we rethink the ciphertext equality check step of the decapsulation procedure of Saber, which is one out of four KEM finalists in the third round NIST PQC standardization process. Through this investigation, we pursue cryptographic answers to some important questions. Those are why the re-encryption process of Fujisaki-Okamoto transformation, which is commonly used method to satisfy IND-CCA security in most existing lattice-based KEM algorithms including Saber, is especially necessary in the case of Saber, whether the re-encryption process can be further simplified, and whether the ciphertext equality check must be performed over the entire (re-encrypted/originally received) ciphertexts?

Johanna Henrich, Andreas Heinemann, Alexander Wiesmaier +1 more