密钥封装机制的抗量子安全性设计理论

Haodong Jiang, Zhenfeng Zhang, Long Chen, Hong Wang, Zhi Ma (2018): IND-CCA-Secure Key Encapsulation Mechanism in the Quantum Random Oracle Model, Revisited. CRYPTO 2018: 96-125

在美国国家标准技术研究院的抗量子密码标准化征集活动中，进入第一轮评估的64个抗量子密码算法中有25个是密钥封装机制。这些候选算法的构造一般给出满足弱安全性（IND-CPA或OW-CPA）的设计，然后通过应用一些通用变换得到强安全性（IND-CCA）的密钥封装机制。为了全面评估抗量子安全性，人们期待密钥封装机制的抗量子安全性设计理论，特别是量子随机预言模型（QROM）下的安全性分析。然而，当前这些算法要么没有QROM下的安全性分析，要么采用了Targhi和Unruh的设计理论，通过在密文中增加一个额外的长度保持杂凑组件来达到QROM安全性。美国Mike Hamburg等猜想Targhi-Unruh杂凑组件是不必要的，但没有给出理论依据。

我们研究了密钥封装机制构造中广泛使用的两类通用变换技术的抗量子安全性，通过一种新颖的证明技术，在QROM下证明了其IND-CCA安全性，无需引入额外的长度保持杂凑组件，而且得到了更紧的安全界，将安全性归约损失由Targhi-Unruh设计方法的4次降为2次。这一方法具有通用性，适用于各类抗量子密码算法。该结果不仅为美国NIST抗量子密码标准征集计划的16个候选算法的抗量子安全性提供坚实的理论支撑，解决了Hamburg提出的猜想，而且可以为一系列候选算法提供优化设