### Post-Quantum Anonymity of Kyber

##### Abstract

Kyber is a key-encapsulation mechanism (KEM) that was recently selected by NIST in its PQC standardization process; it is also the $$\textit{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 $$\textit{anonymity}$$ (Bellare $$\textit{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 $$\textit{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 $$\textit{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 $$\textit{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)
Category
Public-key cryptography
Publication info
Preprint.
Keywords
anonymity post-quantum cryptography NIST PQC standardization KEM hybrid PKE quantum random oracle model
Contact author(s)
vmaram @ inf ethz ch
keita xagawa zv @ hco ntt co jp
History
2022-12-10: approved
See all versions
Short URL
https://ia.cr/2022/1696

CC BY

BibTeX

@misc{cryptoeprint:2022/1696,
author = {Varun Maram and Keita Xagawa},
title = {Post-Quantum Anonymity of Kyber},
howpublished = {Cryptology ePrint Archive, Paper 2022/1696},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/1696}},
url = {https://eprint.iacr.org/2022/1696}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.