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

Morgan State University, Baltimore MD

Investigators

Abstract

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.