CAREER: Quantum Algorithms and Classical Cryptography

理解量子计算机能比经典计算机更快地解决哪些问题是一个基本问题。众所周知，量子计算机可以破解广泛使用的密码系统，包括用于电子商务交易的密码系统，但寻找新的有用应用是一项具有挑战性和重要的任务。确定量子计算机无法破解哪些密码系统也同样重要。这一点很重要，因为即使在量子计算机建成之后，今天的加密信息也应该保持安全。这个项目将解决这两个问题。第一部分将专注于在量子计算机上找到比经典计算机具有指数级更快算法的新问题。存在潜在指数加速的问题包括图同构问题、唯一最短格向量问题和非abel隐子群问题。该项目的第二部分将研究哪些经典密码系统在量子计算机的存在下仍然是安全的。这需要理解量子计算机的局限性。现代密码学依赖于假设某些问题无法在经典计算机上解决，而量子计算机也必须识别出这一集。一些现有的系统，如基于格的密码系统，还没有得到充分的研究。其他问题包括零知识证明和伪随机数生成器抵御量子攻击的安全性。

Understanding which problems quantum computers can solve faster than classical computers is a fundamental problem. It is known that quantum computers can break widely used cryptosystems, including those used for e-commerce transactions, but finding new useful applications is a challenging and important task. It is equally important to determine which cryptosystems quantum computers cannot break. This is important since today's encrypted information should remain secure even after quantum computers have been built. This project will address these two issues. The first part will focus on finding new problems that have exponentially faster algorithms on quantum computers than on classical computers. Problems where a potential exponential speedup exists include graph isomorphism, the unique shortest lattice vector problem, and the nonabelian hidden subgroup problem. The second part of this project will study which classical cryptosystems remain secure in the presence of quantum computers. This requires understanding the limitations of quantum computers. Modern cryptography relies on assuming that certain problems cannot be solved on classical computers, and this set must also be identified for quantum computers. Some existing systems, such as lattice-based cryptosystems, have not been sufficiently studied. Other questions include the security of zero-knowledge proofs and pseudo-random number generators against quantum attacks.