Collaborative Research: EMT/QIS: Quantum Algorithms and Post-Quantum Cryptography

合作研究：EMT/QIS：量子算法和后量子密码学项目摘要密码学是实现电子交易隐私和安全的基本基础设施元素。然而，当大规模量子计算机最终建成时，它将迫使我们放弃今天常用的RSA和Diffie-Hellman等既定的密码学方法。这项拟议的研究将进一步推进这一颠覆性量子算法研究；但它也旨在建立一个新的安全后量子密码学框架，以维护这一社会关键基础设施。拯救现代密码学最有吸引力的方法将是开发经典密码系统，即使面对量子对手，我们也有令人信服的安全证据。PI和他们的合作者最近的工作表明，即使对于量子算法，某些代数问题也具有困难性质。我们建议加强和利用这些结果来开发可以在今天的计算机上执行的密码方案，但在未来即使在量子攻击下也仍然是安全的。同时，我们建议开发新的量子算法来破解基于辫子群中的共轭的密码系统。这是为数不多的尚未被证明易受量子攻击的经典密码系统之一。我们的研究计划还直接与所有四个机构的研究生培养、本科生教育创新、教育推广和广泛的科学传播相结合。

Collaborative Research: EMT/QIS:Quantum Algorithms and Post-Quantum CryptographyProject SummaryCryptography is the basic infrastructural element enabling privacy and security for electronic transactions. However, when a large-scale quantum computer is finally built, it will force us to abandon established methods of cryptography, such as RSA and Diffie-Hellman, which are in common use today. The proposed research will further this line of disruptive quantum algorithmic research; but it also aims to erect a new framework of secure post-quantum cryptography, in order to maintain this societally critical infrastructure.The most attractive approach for salvaging modern cryptography would be to develop classical cryptosystems for which we have compelling evidence of security even in the face of quantum adversaries. Recent work by the PIs and their collaborators has shown that certain algebraic problems possess hardness properties relevant even for quantum algorithms. We propose to strengthen and leverage these results in order to develop cryptographic schemes which can be carried out by today's computers, but which will remain secure even against quantum attack in the future.In tandem with this effort, we propose to develop new quantum algorithms for breaking cryptosystems based on conjugacy in the braid group. This is one of the few remaining classical cryptosystems which has not already been shown to be vulnerable to quantum attack.Our research program is also directly integrated with graduate student training at all four institutions, undergraduate educational innovation, educational outreach, and broad scientific dissemination.