EAGER: SaTC: Post-Quantum Indifferentiability

当前用于保护因特网流量的技术依赖于基于两个数学问题--因子分解问题和离散对数问题--的假定难度的密码协议。然而，量子计算机的新兴技术-一种利用量子力学定律比经典计算机更快地执行某些计算的计算机-可以有效地解决这两个问题，从而有效地攻击相应的加密协议。预计量子计算机的出现，标准化新的量子安全（也称为“后量子”）密码协议的努力正在进行中。值得注意的是，量子攻击不仅使基于因子分解和离散对数的密码系统不安全，而且还危及采用称为“随机预言方法”的技术的密码系统的安全性。“这种方法假设所有各方都可以访问称为随机预言机的理想对象，并且在随机预言机模型中分析密码系统的安全性。随机预言机模型中的经典安全证明在量子设置中失败，因为对预言机的量子叠加查询允许改进的攻击。该项目将通过不可微性框架的量子模拟来开发基于随机预言的后量子密码系统的安全性分析的关键工具。在随机预言模型中分析经典密码系统安全性的基本工具包括证明所谓的构造不可微性。不可微性的概念形式化了构造所需的属性，以安全地替换任意密码系统中的理想对象（如随机预言机）。虽然经常被认为是理所当然的，不可微的结果从经典的设置不一定扩展到量子设置。此外，量子环境对证明不可微性提出了独特的障碍，这使得整个不可微性技术是否适用于量子预言环境成为疑问。这个项目探讨了在量子预言机环境中不可微性框架的可能性。具体而言，该项目包括以下技术问题：（1）确定广义不可能性结果是否适用于量子不可微性设置;（2）开发证明量子不可微性的新技术;（3）定义新的形式安全模型，用于分析量子预言模型中的对称和公钥密码系统;（4）根据量子不可微性或新引入的正式模型分析基本结构的安全性。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估而被认为值得支持。

Current technology for securing Internet traffic relies on cryptographic protocols that are based on the presumed difficulty of two mathematical problems - the factorization problem and the discrete logarithm problem. However, the emerging technology of quantum computers - a type of computer that leverages the laws of quantum mechanics to perform certain computations faster than classical computers - can efficiently solve both of these problems and thus effectively attack the respective cryptographic protocols. Anticipating the advent of quantum computers, efforts to standardize new quantum-safe (also called "post-quantum") cryptographic protocols are in progress. It is important to note that quantum attacks not only render factoring and discrete-logarithm based cryptosystems insecure, but also compromise the security of cryptosystems employing a technique known as the "random oracle methodology." This methodology assumes that all parties have access to an ideal object known as a random oracle and the security of the cryptosystem is analyzed in the random oracle model. Classical security proofs in the random oracle model fail in the quantum setting since quantum superposition queries to the oracle allow for improved attacks. This project will develop crucial tools for the security analysis of random oracle based, post-quantum cryptosystems by means of a quantum analogue of the indifferentiability framework.A fundamental tool for analyzing the security of classical cryptosystems in the random oracle model involves proving the so-called indifferentiability of constructions. The notion of indifferentiability formalizes the properties required of a construction to securely replace an ideal object (such as a random oracle) in arbitrary cryptosystems. Although often taken for granted, indifferentiability results from the classical setting do not necessarily extend to the quantum setting. Moreover, the quantum setting presents unique obstacles to proving indifferentiability, leaving in doubt whether the entire indifferentiability technique is applicable in the quantum oracle setting. This project explores the possibility of an indifferentiability framework in the quantum oracle setting. Specifically, the project encompasses the following technical problems: (1) Determining whether or not broad impossibility results apply to the quantum indifferentiability setting; (2) Developing new techniques for proving quantum indifferentiability; (3) Defining new formal security models for the analysis of symmetric and public key cryptosystems in the quantum oracle model; (4) Analyzing the security of essential constructions with respect to quantum indifferentiability or the newly introduced formal models.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.