Anonymous, Robust Post-quantum Public Key Encryption

A core goal of the NIST PQC competition is to produce public-key encryption (PKE) schemes which, even if attacked with a large-scale quantum computer, maintain the security guarantees needed by applications. The main security focus in the NIST PQC context has been IND-CCA security, but other applications demand that PKE schemes provide anonymity (Bellare et al., ASIACRYPT 2001), and robustness (Abdalla et al., TCC 2010). Examples of such applications include anonymous communications systems, cryptocurrencies, anonymous credential systems, searchable encryption, and auction protocols. Almost nothing is known about how to build post-quantum PKE schemes offering these security properties. In particular, the status of the NIST PQC finalists with respect to anonymity and robustness is unknown. This paper offers a systematic study of anonymity and robustness for post-quantum PKE schemes. We focus on two theoretical aspects. Firstly, we study the crucial role of implicit/explicit rejection for the KEM used in the standard KEM-DEM paradigm and how it affects anonymity and robustness of the resulting PKE scheme. Secondly, we examine how the Fujisaki-Okamoto (FO) transforms (Fujisaki and Okamtoto, Journal of Cryptology 2013) confer robustness and enhance weak anonymity of a base PKE scheme to strong anonymity for the resulting KEM. We then leverage our theoretical results to study the anonymity and robustness of the four NIST finalists: Classic McEliece, Kyber, NTRU and Saber. We exhibit a striking property of the PKE scheme obtained from the Classic McEliece KEM using the standard KEM-DEM construction: for any message m, we can construct a single hybrid ciphertext c which decrypts to the chosen m under any Classic McEliece private key. This highlights that Classic McEliece does not lead to a robust PKE scheme and presents a barrier to using our proof techniques to establish the anonymity of Classic McEliece. As a side-result of our treatment, we identify (and repair) technical gaps in the IND-CCA security claims for Saber; we also provide positive anonymity and robustness results for Saber. Similarly, we identify issues with the IND-CCA security claims for Kyber; these also act as a barrier to proving its anonymity. Finally, we describe technical barriers to applying our techniques to NTRU. Our work, as well as being of theoretical interest, directly contributes to the broad-spectrum evaluation of NIST candidate algorithms.