International Association for Cryptologic Research

International Association
for Cryptologic Research


Post-Quantum Anonymity of Kyber

Varun Maram , ETH Zurich
Keita Xagawa , NTT Social Informatics Laboratories
DOI: 10.1007/978-3-031-31368-4_1
Search ePrint
Search Google
Presentation: Slides
Conference: PKC 2023
Award: Best paper award
Abstract: Kyber is a key-encapsulation mechanism (KEM) that was recently selected by NIST in its PQC standardization process; it is also the only scheme to be selected in the context of public-key encryption (PKE) and key establishment. The main security target for KEMs, and their associated PKE schemes, in the NIST PQC context has been IND-CCA security. However, some important modern applications also require their underlying KEMs/PKE schemes to provide anonymity (Bellare et al., ASIACRYPT 2001). Examples of such applications include anonymous credential systems, cryptocurrencies, broadcast encryption schemes, authenticated key exchange, and auction protocols. It is hence important to analyze the compatibility of NIST's new PQC standard in such "beyond IND-CCA" applications. Some starting steps were taken by Grubbs et al. (EUROCRYPT 2022) and Xagawa (EUROCRYPT 2022) wherein they studied the anonymity properties of most NIST PQC third round candidate KEMs. Unfortunately, they were unable to show the anonymity of Kyber because of certain technical barriers. In this paper, we overcome said barriers and resolve the open problems posed by Grubbs et al.(EUROCRYPT 2022) and Xagawa (EUROCRYPT 2022) by establishing the anonymity of Kyber, and the (hybrid) PKE schemes derived from it, in a post-quantum setting. Along the way, we also provide an approach to obtain tight IND-CCA security proofs for Kyber with concrete bounds; this resolves another issue identified by the aforementioned works related to the post-quantum IND-CCA security claims of Kyber from a provable security point-of-view. Our results also extend to Saber, a NIST PQC third round finalist, in a similar fashion.
  title={Post-Quantum Anonymity of Kyber},
  author={Varun Maram and Keita Xagawa},