In this work we study the quantum security of public key encryption schemes (PKE). Boneh and Zhandry (CRYPTO'13) initiated this research area for PKE and symmetric key encryption (SKE), albeit restricted to a classical indistinguishability phase. Gagliardoni et al. (CRYPTO'16) advanced the study of quantum security by giving, for SKE, the first definition with a quantum indistinguishability phase. For PKE, on the other hand, no notion of quantum security with a quantum indistinguishability phase exists. Our main result is a novel quantum security notion (qINDqCPA) for PKE with a quantum indistinguishability phase, which closes the aforementioned gap. We show a distinguishing attack against code-based schemes and against LWE-based schemes with certain parameters. We also show that the canonical hybrid PKE-SKE encryption construction is secure, even if the underlying PKE scheme by itself is not. Finally, we classify quantum-resistant PKE schemes based on the applicability of our security notion and discuss concurrent and independent work. Our core idea follows the approach of Gagliardoni et al. by using so-called type-2 operators for encrypting the challenge message. At first glance, type-2 operators appear unnatural for PKE, as the canonical way of building them requires both the secret and the public key. However, we identify a class of PKE schemes - which we call recoverable - and show that for this class type-2 operators require merely the public key. Moreover, recoverable schemes allow to realise type-2 operators even if they suffer from decryption failures, which in general thwarts the reversibility mandated by type-2 operators. Our work reveals that many real-world quantum-resistant PKE schemes, including most NIST PQC candidates and the canonical hybrid construction, are indeed recoverable.

翻译：在这项工作中,我们研究了公用钥匙加密计划(PKE)的量子安全。Boneh和Zhandry(CRYPTO'13)启动了PKE和对称钥匙加密(SKE)的这个研究领域,尽管仅限于传统的分化阶段。Gagliardoni et al.(CRYPTO'16)为SKE提供了量子安全的第一个定义,给SKE提供了不可分化阶段的量子安全。对PKE来说,不存在具有可分化阶段的量级安全概念。我们的主要结果是PKE的量安全新概念(QINDQCPA),而PKE的量级加密概念(QQQQ)只是一个无法分化的典型。我们展示了对基于代码的计划和基于LWE的计划(CE)的区别性研究,我们同时展示了PKE-S-KE加密的量级混合加密的加密结构,即使基本的PKE计划本身不是。最后,我们根据“可逆性PKE-2”计划(QE)的量级的量级的量级安全概念, 系统(Q)的可操作操作者也能够同时展示。