Paper 2021/1323

Anonymity of NIST PQC Round 3 KEMs

Keita Xagawa

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 one 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in Eurocrypt 2022
Keywords
anonymityrobustnesspost-quantum cryptographyNIST PQC standardizationKEMPKE
Contact author(s)
keita xagawa zv @ hco ntt co jp
History
2022-04-01: last of 2 revisions
2021-10-05: received
See all versions
Short URL
https://ia.cr/2021/1323
License
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.