Make Quantum Indistinguishability Great Again
Tommaso Gagliardoni, Juliane Krämer, Patrick Struck
In this work we study the (superposition-based, or QS2) quantum security of public key encryption schemes, originally initiated by Boneh and Zhandry (CRYPTO 2013, for a classical challenge indistinguishability phase) and imprioved by Gagliardoni et al. (CRYPTO 2016, for the symmetric key case). For public key encryption schemes, no notion of quantum security with a quantum indistinguishability phase exists. In this work we close this gap by using so-called type-2 operators for encrypting the challenge message. This brings non-trivial obstacles: On the one hand, public key encryption schemes typically cannot recover the randomness during decryption. On the other hand, many real-world schemes suffer from a small probability of decryption failures. Nevertheless, we identify a class of encryption schemes, which we call recoverable, that allow to avoid decryption failures given knowledge of the original encryption randomness, and we show that for these schemes the type-2 operator can be efficiently implemented even without knowledge of the secret key. This means that, for the public key case, type-2 operators are actually very natural. We also observe that many real-world quantum-resistant schemes, including many NIST candidates, are of this type. Equipped with these results, we (1) give the first quantum security notion (qINDqCPA) for public key encryption with a quantum indistinguishability phase, (2) prove that the canonical LWE-based encryption scheme achieves our security notion, (3) show that our notion is strictly stronger than existing security notions, (4) study the general classification of quantum-resistant public key encryption schemes, and (5) compare our results to a concurrent and independent work by Chevalier et al. (2020).
arXiv:2003.00578•Mar 1, 2020•1 citation