Key Quantum Algorithms: Shor’s, Grover’s, and Applications

Gaurav Raj, Dheerendra Singh, Abhishek Madaan

Ch. Vijay Anil Dai, T. Niranjan Kumar, M.P.D.Parimala M.P.D.Parimala +1 more

Melinda Andrews, Joseph Stephen Dulny, Andrew N. Glaudell +6 more

Alexei Petrenko, Sergei Petrenko

In quantum cryptanalysis, Shor's algorithm provides exponential acceleration of solving factorization problems, discrete logarithm problem, and elliptic curve discrete logarithm problems, widely used in cryptographic applications in cyberspace. Shor's quantum algorithm can potentially crack most protocols and schemes of asymmetric encryption (public key cryptography). In general, all known quantum algorithms can be divided into two groups: providing exponential gain (for example, Shor's algorithm) and providing quadratic gain (for example, Grover's algorithm). Particular attention is paid to the Shor quantum algorithm and other polynomial algorithms capable of solving cryptanalysis problems with the required reliability and complexity in polynomial time. For quantum computing, all cryptographies are divided into quantum-secure and quantum-insecure. Algorithms and cryptosystems of symmetric encryption are attributed to quantum-secure but with at least twice the key length increased. This chapter presents an overview of the concepts discussed in the subsequent chapters of this book.

Matt W. Hayward

Rudolf Sinaga, Uswatun Kasanah

Quantum computing has emerged as a revolutionary paradigm, holding immense potential to solve complex problems that classical computing struggles to address. This study explores the application of quantum computing in cryptography, with a specific focus on two major quantum algorithms: Shor’s algorithm for large number factorization and Grover’s algorithm for unstructured database searching. The main objective of this research is to compare the performance of these quantum algorithms with classical cryptographic methods in terms of computational efficiency and time. Shor’s algorithm, which can factorize large numbers in polynomial time, presents a significant threat to the security of public-key cryptosystems such as RSA, which rely on the difficulty of factoring large numbers. On the other hand, Grover’s algorithm offers a quadratic speedup for searching unstructured databases, making it highly relevant for symmetric key cryptography systems like AES. In this study, simulations of both algorithms were conducted using quantum simulators to assess their speed and effectiveness in solving cryptographic challenges. The results demonstrate that quantum algorithms significantly reduce the computation time compared to classical methods, with Shor’s algorithm efficiently solving factorization problems and Grover’s algorithm accelerating key searching processes. However, while these quantum algorithms show promise in improving cryptographic systems, the implementation of large-scale quantum computers remains a challenge. This research highlights the potential of quantum computing to revolutionize data security and underscores the need for further development in quantum algorithms and the transition to quantum-resistant cryptographic systems to safeguard against the threat posed by quantum computers.