Anonymous, Robust Post-Quantum Public Key Encryption 📺
A core goal of the NIST PQC competition is to produce 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 cryptocurrencies, searchable encryption, and auction protocols. However, almost nothing is known about how to build post-quantum PKE schemes offering these security properties. In particular, the status of the NIST PQC candidates with respect to anonymity and robustness is unknown. This paper initiates a systematic study of anonymity and robustness for post-quantum PKE schemes. Firstly, we identify implicit rejection as a crucial design choice shared by most post-quantum KEMs, show that implicit rejection renders prior results on anonymity and robustness for KEM-DEM PKEs inapplicable, and transfer prior results to the implicit-rejection setting where possible. Secondly, since they are widely used to build post-quantum PKEs, we examine how the Fujisaki-Okamoto (FO) transforms (Fujisaki and Okamoto, Journal of Cryptology 2013) confer robustness and enhance weak anonymity of a base PKE. We then leverage our theoretical results to study the anonymity and robustness of three NIST KEM finalists---Saber, Kyber, and Classic McEliece---and one alternate, FrodoKEM. Overall, our findings for robustness are definitive: we provide positive robustness results for Saber, Kyber, and FrodoKEM, and a negative result for Classic McEliece. Our negative result stems from a striking property of KEM-DEM PKE schemes built with the Classic McEliece KEM: for any message 'm', we can construct a single hybrid ciphertext 'c' which decrypts to the chosen 'm' under any Classic McEliece private key. Our findings for anonymity are more mixed: we identify barriers to proving anonymity for Saber, Kyber, and Classic McEliece. We also found that in the case of Saber and Kyber, these barriers lead to issues with their IND-CCA security claims. We have worked with the Saber and Kyber teams to fix these issues, but they remain unresolved. On the positive side, we were able to prove anonymity for FrodoKEM and a variant of Saber introduced by D'Anvers et al. (AFRICACRYPT 2018). Our analyses of these two schemes also identified technical gaps in their IND-CCA security claims, but we were able to fix them.
On the Quantum Security of OCB
The OCB mode of operation for block ciphers has three variants, OCB1, OCB2 and OCB3. OCB1 and OCB3 can be used as secure authenticated encryption schemes whereas OCB2 has been shown to be classically insecure (Inoue et al., Crypto 2019). Even further, in the presence of quantum queries to the encryption functionality, a series of works by Kaplan et al. (Crypto 2016), Bhaumik et al. (Asiacrypt 2021) and Bonnetain et al. (Asiacrypt 2021) have shown how to break the unforgeability of the OCB modes. However, these works did not consider the confidentiality of OCB in the presence of quantum queries.We fill this gap by presenting the first formal analysis of the IND-qCPA security of OCB. In particular, we show the first attacks breaking the IND-qCPA security of the OCB modes. Surprisingly, we are able to prove that OCB2 is IND-qCPA secure when used without associated data, while relying on the assumption that the underlying block cipher is a quantum-secure pseudorandom permutation. Additionally, we present new quantum attacks breaking the universal unforgeability of OCB. Our analysis of OCB has implications for the post-quantum security of XTS, a well-known disk encryption standard, that was considered but mostly left open by Anand et al. (PQCrypto 2016).
Gladius: LWR based efficient hybrid public key encryption with distributed decryption 📺
Standard hybrid encryption schemes based on the KEM-DEM framework are hard to implement efficiently in a distributed manner whilst maintaining the CCA security property of the scheme. This is because the DEM needs to be decrypted under the key encapsulated by the KEM, before the whole ciphertext is declared valid. In this paper we present a new variant of the KEM-DEM framework, closely related to Tag-KEMs, which sidesteps this issue. We then present a post-quantum KEM for this framework based on Learning-with-Rounding, which is designed specifically to have fast distributed decryption. Our combined construction of a hybrid encryption scheme with Learning-with-Rounding based KEM, called Gladius, is closely related to the NIST Round 3 candidate called Saber. Finally, we give a prototype distributed implementation that achieves a decapsulation time of 4.99 seconds for three parties.