International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Anonymity of NIST PQC Round 3 KEMs

Authors:
Keita Xagawa , NTT Social Informatics Laboratories
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2022
Abstract: This paper investigates \emph{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.
Video from EUROCRYPT 2022
BibTeX
@inproceedings{eurocrypt-2022-31913,
  title={Anonymity of NIST PQC Round 3 KEMs},
  publisher={Springer-Verlag},
  author={Keita Xagawa},
  year=2022
}