Anonymity of NIST PQC Round 3 KEMs

Keita Xagawa

Paper 2021/1323

Anonymity of NIST PQC Round 3 KEMs

Keita Xagawa

, NTT Social Informatics Laboratories

Abstract

This paper investigates __anonymity__ of all NIST PQC Round 3 KEMs: Classic McEliece, Kyber, NTRU, Saber, BIKE, FrodoKEM, HQC, NTRU Prime (Streamlined NTRU Prime and NTRU LPRime), and SIKE. We show the following results: * NTRU is anonymous in the quantum random oracle model (QROM) if the underlying deterministic PKE is strongly disjoint-simulatable. NTRU is collision-free in the QROM. A hybrid PKE scheme constructed from NTRU as KEM and appropriate DEM is anonymous and robust. (Similar results for BIKE, FrodoKEM, HQC, NTRU LPRime, and SIKE hold except for two of three parameter sets of HQC.) * Classic McEliece is anonymous in the QROM if the underlying PKE is strongly disjoint-simulatable and a hybrid PKE scheme constructed from it as KEM and appropriate DEM is anonymous. * Grubbs, Maram, and Paterson pointed out that Kyber and Saber have a gap in the current IND-CCA security proof in the QROM (EUROCRYPT 2022). We found that Streamlined NTRU Prime has another technical obstacle for the IND-CCA security proof in the QROM. Those answer the open problem to investigate the anonymity and robustness of NIST PQC Round~3 KEMs posed by Grubbs, Maram, and Paterson (EUROCRYPT 2022). We use strong disjoint-simulatability of the underlying PKE of KEM and strong pseudorandomness and smoothness/sparseness of KEM as the main tools, which will be of independent interest.

Note: This paper supersedes https://eprint.iacr.org/2021/741. Update: Correct bounds and the results on HQC.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: A major revision of an IACR publication in EUROCRYPT 2022
Keywords: anonymity robustness post-quantum cryptography NIST PQC standardization KEM PKE
Contact author(s): keita xagawa zv @ hco ntt co jp
History: 2022-09-22: last of 3 revisions; 2021-10-05: received; See all versions
Short URL: https://ia.cr/2021/1323
License: CC BY

BibTeX

@misc{cryptoeprint:2021/1323,
      author = {Keita Xagawa},
      title = {Anonymity of NIST PQC Round 3 KEMs},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1323},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1323}},
      url = {https://eprint.iacr.org/2021/1323}
}