Excellence in Research: Optimizing Quantum Circuits for Fast Cryptanalyzing Pre-Quantum Encryptions and Securing Post-Quantum Cryptographies

卓越的研究：优化量子电路以快速分析前量子加密并保护后量子加密

• 批准号: 2000136
• 负责人: Shuangbao Wang
• 金额: $ 30.94万
• 依托单位: Morgan State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-05-01 至 2024-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2000136&HistoricalAwards=false
• 关键词: Excellence; Research; Optimizing; Quantum; Circuits

This project promotes the progress of science in quantum computing algorithms and cryptologic techniques in order to improve security of encrypted information, which will have national security and defense applications. Currently, the commonly used encryption algorithms such as RSA are considered “unbreakable” by modern digital computers due to the complexity of computation that would be required. However, this may change in the next decade or so in light of advances in quantum science. Quantum mechanics has led to the discovery that considerable numbers of states can be manipulated at the same time thus significantly reduce the amount of time in processing. New quantum computers have shown the baseline of “quantum supremacy” in solving problems that classical digital computers practically cannot. Efficient quantum algorithms are key to enable computer scientists to take full advantage of the next generation of practical quantum computers to efficiently solve today’s unsolvable problems. Advances in quantum science in both breaking and securing the encryptions are paramount for national security and preventing adversaries from taking advantage of critical areas of national defense. This project seeks to discover efficient quantum cryptologic methods (i.e. the art of revealing the secret) and secure quantum cryptographic techniques (i.e. the science of making the secret more secure). This project not only exhibits the excellence in scientific research, but also supports diversity and inclusion goals for the benefit of society. Quantum cryptoanalysis plays an important role in finding vulnerabilities of existing crypto systems. It can also become an effective tool in fighting adversaries in cyber operations. Efficient quantum algorithms are indispensable to the utilization of quantum computer resources to solve today’s unsolvable problems. It has the potential to break the current crypto systems such as RSA with the advances of next-generation quantum computers. Currently, most quantum cryptanalytic algorithms have limited capability to factor multiple integers due to the fact that each Quantum Fourier Transform (QFT), the speed machine to find out a period of a particular integer, requires a unique quantum circuit. According to Shor’s algorithm, once the period is found, finding factors (crypto keys) becomes easy. To break the RSA encryption, one needs to design a unique quantum circuit for each integer being exploited. Since there are a large number of integers to exploit, the current one integer-one circuit factor finding approach is not practically useful. This project aims to discover techniques to automatically generate quantum circuits and factor multiple integers at once. The research also explores how artificial intelligence can assist in designing efficient quantum algorithms and test those algorithms using quantum simulators and on real quantum computers. Computational-wise, the project speeds up the cryptanalytic process by improving the order of approximation significantly on top of a polynomial degree that the QFT has saved from the unsolvable exponential degree. The findings from this research will have significant impact on both quantum cryptology and quantum cryptography. This research seeks to transform cryptanalytic study from theoretical to practical, and improve the integrity of the next-generation Quantum Internet.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.

该项目推动了量子计算算法和密码学技术的科学进步，以提高加密信息的安全性，具有国家安全和国防应用价值。目前，由于所需的计算复杂性，现代数字计算机认为常用的加密算法(如RSA)是“牢不可破的”。然而，随着量子科学的进步，这种情况可能会在未来十年左右发生变化。量子力学导致人们发现，可以同时操纵相当数量的状态，从而显著减少处理的时间。新的量子计算机在解决经典数字计算机实际上无法解决的问题时，已经显示出“量子至上”的底线。高效的量子算法是让计算机科学家充分利用下一代实用量子计算机高效解决当今无法解决的问题的关键。量子科学在破解和保护加密方面的进展对国家安全和防止对手利用国防关键领域至关重要。这个项目寻求发现有效的量子密码学方法(即揭示秘密的艺术)和安全的量子密码技术(即使秘密更安全的科学)。该项目不仅展示了科学研究的卓越，而且支持多样性和包容性的目标，造福社会。量子密码分析在发现现有密码系统的漏洞方面发挥着重要作用。它还可以成为在网络行动中打击对手的有效工具。高效的量子算法对于利用量子计算机资源来解决当今无法解决的问题是不可或缺的。随着下一代量子计算机的进步，它有可能打破目前的密码系统，如RSA。目前，大多数量子密码分析算法对多个整数的分解能力有限，因为每个量子傅里叶变换(QFT)都需要唯一的量子电路。QFT是找出特定整数周期的速度机器。根据Shor的算法，一旦找到周期，查找因子(密码密钥)就变得很容易。要破解RSA加密，需要为每个被利用的整数设计唯一的量子电路。由于有大量的整数可供利用，因此当前的一整一电路因数求取方法在实际中并不有用。该项目旨在发现自动生成量子电路并同时对多个整数进行因式分解的技术。这项研究还探索了人工智能如何帮助设计高效的量子算法，并使用量子模拟器和真实的量子计算机测试这些算法。在计算方面，该项目通过在QFT从不可解的指数度中节省的多项式次数的基础上显著提高了逼近阶，从而加快了密码分析过程。这项研究的发现将对量子密码学和量子密码学产生重大影响。这项研究旨在将密码分析研究从理论转化为实践，并提高下一代量子互联网的完整性。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Code Structures for Quantum Encryption and Decryption

• DOI: 10.1109/csp51677.2021.9357606
• 发表时间: 2021-01
• 期刊: 2021 IEEE 5th International Conference on Cryptography, Security and Privacy (CSP)
• 作者: E. Sakk;S. Wang

Quantum Algorithms: Overviews, Foundations, and Speedups

量子算法：概述、基础和加速

• 发表时间: 2021
• 期刊: Security and Privacy
• 影响因子: 1.9
• 作者: Wang, Shuangbao Paul;Sakk, Eric
• 通讯作者: Sakk, Eric

Quantum Cryptography and Simulation: Tools and Techniques

量子密码学和模拟：工具和技术

• DOI: 10.1145/3377644.3377671
• 发表时间: 2020
• 期刊: Security and Privacy
• 影响因子: 1.9
• 作者: Wang, Shuangbao;Rohde, Matthew;Ali, Amjad
• 通讯作者: Ali, Amjad