论文标题
公共密钥加密的量子不可区分性
Quantum Indistinguishability for Public Key Encryption
论文作者
论文摘要
在这项工作中，我们研究了公钥加密方案（PKE）的量子安全性。 Boneh和Zhandry（Crypto'13）启动了该研究领域的PKE和对称密钥加密（SKE），尽管仅限于经典的不可区分性阶段。 Gagliardoni等。 （Crypto'16）通过给出SKE的第一个定义，以量子不可区分性阶段给出了量子安全性的研究。另一方面，对于PKE而言，不存在具有量子不可分性阶段的量子安全性概念。我们的主要结果是针对PKE的新型量子安全概念（QIND-QCPA），具有量子不可区分的阶段，它缩小了上述间隙。我们展示了针对基于代码的方案以及具有某些参数的基于LWE的方案的区别攻击。我们还表明，即使不是基本的PKE方案本身不是，规范混合PKE-SKE加密结构也是QIND-QCPA-SECURE。最后，我们根据我们的安全概念的适用性对抗量子的PKE方案进行了分类。我们的核心思想遵循了Gagliardoni等人的方法。通过使用所谓的2型操作员来加密挑战消息。乍看之下，2型操作员对于PKE来说似乎是不自然的，因为构建它们的规范方式需要秘密和公钥。但是，我们确定了一类PKE计划（我们称之为可回收），并表明对于此类类型2的操作员仅需要公钥。此外，即使他们患有解密失败，可回收的方案也可以实现2型操作员，这通常会阻止2型操作员规定的可逆性。我们的工作表明，许多现实世界中Quantum Quantum Peke方案，包括大多数NIST PQC候选者和规范的混合构建，确实是可回收的。
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 (qIND-qCPA) 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 qIND-qCPA-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. 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.
