Paper 2022/1696

Post-Quantum Anonymity of Kyber

Varun Maram, ETH Zurich
Keita Xagawa, NTT Social Informatics Laboratories, Japan

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.

Available format(s)
Public-key cryptography
Publication info
A minor revision of an IACR publication in PKC 2023
anonymitypost-quantum cryptographyNIST PQC standardizationKEMhybrid PKEquantum random oracle model
Contact author(s)
vmaram @ inf ethz ch
keita xagawa zv @ hco ntt co jp
2023-02-13: revised
2022-12-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Varun Maram and Keita Xagawa},
      title = {Post-Quantum Anonymity of Kyber},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1696},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.