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的法定任务，并通过评估智力的智力优点和更广泛的影响来评估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 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

Quantum Algorithms: Overviews, Foundations, and Speedups

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

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