Eastern-European Journal of Enterprise Technologies

Analysis of the possibility of quantum computers and quantum computings for cryptanalysis of modern cryptosystems

Юрій Іванович Горбенко, Роман Сергійович Ганзя

Published Feb 5, 2014• 3 citations

Abstract

The main trends of the science and technology development in the field of quantum physics and quantum calculations are considered in the paper. It has been shown that over the past few years plenty of new discoveries and achievements have been made in the field of quantum physics, all these events, anyway, had a great influence on the invention and production of quantum computers. Many communities around the world have been engaged in the development of quantum computers and some of them have achieved significant results in it by now.It is shown that using quantum algorithms of Shor and Grover, which can be fulfilled on a properly implemented quantum computer, can compromise some symmetric and asymmetric cryptosystems. The analysis results of endurance of the known block ciphers regarding the quantum cryptanalysis are given. It is also shown that some of them are not able to resist the quantum cryptanalysis method based on Grover's algorithm. The analysis of Shor's algorithm possibilities, which can significantly reduces computational costs for solving mathematical problems of endurance of modern asymmetric cryptoalgorithms, is given. Herewith, Shor's quantum algorithm diminishes the complexity of the cryptanalysis from exponential and subexponential to polynomial. In addition, the assessment of quantum computer resources is given in the paper, which are necessary for the quantum cryptanalysis concerning such cryptosystems as DSA, RSA, EC and NTRU.

DOI: 10.15587/1729-4061.2014.19897

Related papers

Development of Quantum Cryptanalysis Algorithms

Alexei Petrenko, Sergei Petrenko

This chapter evaluates the stability of the modern cryptographic algorithms to clarify the tasks of cryptanalysis of asymmetric encryption schemes and digital signature based on factorization and discrete logarithm problems in various algebraic structures in a quantum computing model. It considers the features of modeling quantum cryptanalysis algorithms on a quantum scheme, and shows the differences between these algorithms and classical algorithms. The quantum algorithm is performed by implementing a series of sequential unitary operations. Grover's algorithm provides a quadratic increase in speed, while some other quantum algorithms, for example, the Shor factorization algorithm, give an exponential gain compared to the corresponding classical algorithms. Grover's algorithm is modified into an algorithm for recovering the symmetric encryption key from the message text and ciphertext. The stability of the RSA asymmetric encryption system is based on the super-polynomial computational complexity of factorization of natural numbers. However, there is a quantum algorithm whose complexity is polynomial.

River Publishers eBooksFeb 7, 20233 citations

Quantum Attacks on Modern Cryptography and Post-Quantum Cryptosystems

Zachary Marron

Cryptography is a critical technology in the modern computing industry, but the security of many cryptosystems relies on the difficulty of mathematical problems such as integer factorization and discrete logarithms. Large quantum computers can solve these problems efficiently, enabling the effective cryptanalysis of many common cryptosystems using such algorithms as Shor’s and Grover’s. If data integrity and security are to be preserved in the future, the algorithms that are vulnerable to quantum cryptanalytic techniques must be phased out in favor of quantum-proof cryptosystems. While quantum computer technology is still developing and is not yet capable of breaking commercial encryption, these steps can be taken immediately to ensure that the impending development of large quantum computers does not compromise sensitive data.

Jan 1, 20180 citations

Quantum Computing-Based Cryptanalysis of Cryptographic Algorithms

Jincheng Zhang

This paper investigates the potential impact of quantum computing on the security of currently deployed cryptographic algorithms. The core premise is that the advent of powerful quantum computers, leveraging algorithms like Shor's algorithm and Grover's algorithm, poses a significant threat to widely used public-key cryptosystems and symmetric-key algorithms. We present a theoretical analysis of several key algorithms – RSA, ECC, and AES – examining their vulnerabilities when subjected to quantum attacks. Specifically, we explore the exponential speedup offered by Shor's algorithm for factoring large numbers, the impact on the key size of ECC, and the Grover's algorithm's influence on symmetric key search. Our work highlights the urgency of transitioning to post-quantum cryptography standards to mitigate the risks posed by this technological advancement. The goal is to provide a comprehensive understanding of the landscape of quantum cryptanalysis and its implications for the future of secure communication.

Sep 3, 20260 citations

Quantum Computing for Cryptanalysis: Breaking Modern Cryptographic Protocols

Jessica Roberts, Jennifer Leigh Clarke

Quantum computing poses a fundamental threat to modern cryptographic protocols by exploiting quantum algorithms that surpass classical computational limits. Shor’s algorithm can efficiently factor large integers, breaking RSA and other public-key cryptosystems, while Grover’s algorithm accelerates brute-force attacks against symmetric encryption. As quantum hardware advances, traditional cryptographic schemes risk obsolescence, necessitating the development of quantum-resistant cryptographic techniques. This paper explores the theoretical foundations of quantum cryptanalysis, examining key algorithms, their implications for cybersecurity, and the current state of post-quantum cryptographic solutions. By analyzing resource estimates for quantum attacks and potential mitigation strategies, this study provides a comprehensive overview of the evolving cryptographic landscape in the quantum era.

International Journal on Advanced Electrical and Computer EngineeringApr 15, 20250 citations

Analysis of resistance popular cryptosystems against quantum cryptanalysis based on Grover's algorithm

Юрій Іванович Горбенко, Роман Сергійович Ганзя

The problem of resistance the popular cryptosystemsagainst quantum cryptanalysis is an urgent and importanttask, given the pace of development of quantum technologies.Resistance of all modern cryptosystems based on thecomplexity of solving certain mathematical problems. Suchmathematical problems tend to have exponential complexityor subexponential solutions, using quantum algorithmsthat have been proposed Shore and Grover the complexityof solving such problems is reduced to a polynomial. SoShor's algorithm reduces the complexity of cryptanalysistransformations in the ring, field and in the group of pointson elliptic curves. The article describes the using ofGrover's algorithm for cryptanalysis popular symmetricblock ciphers. The methods of quantum cryptosystemscryptanalysis NTRU, based on a combination of classicalattacks and meeting in the middle of Grover's quantumalgorithm. In this paper we proposed our estimates of resistanceof block popular ciphers and cryptosystemsNTRU with different sizes of the quantum system-wideparameters against cryptanalysis based on the use ofGrover's quantum algorithm. The article also shows thecharacteristics that must have a quantum computer forsuccessful cryptanalysis of certain cryptosystems.

Ukrainian Information Security Research JournalJul 25, 20141 citation

Quantum Computers and Algorithms: A Threat to Classical Cryptographic Systems

Joshua J. Tom, Nlerum Promise Anebo, Bukola Abimbola Onyekwelu +3 more

Contemporary cryptographic algorithms are resistant to the strongest threats to cybersecurity and high-profile cyber-attacks. In recent times, information security scientists and researchers had developed various cryptographic schemes that defeated attacks using the most sophisticated (in terms of processor speed) classical computer. However, this resistance will soon erode with the arrival of quantum computers. In this paper, we profiled quantum computers and quantum algorithms based on their widely believed threat against currently secure cryptographic primitives. We found that Grover’s and Shor’s quantum-based algorithms actually pose a threat to the continued security of symmetric cryptosystems (e.g. 128-bit AES) and asymmetric (public key) cryptosystems (e.g. RSA, Elgamal, elliptic curve Diffie Hellman (ECDH), etc.) respectively.We discovered that the source of the algorithms’ cryptanalytic power against the current systems, stems from the fact that they (Grover and Shor) both equipped their respective algorithms with a quantum circuit component that can execute the oracle in parallel by applying a single circuit to all possible states of an n-qubit input. With this exponential level of processing characteristic of quantum computers and quantum-based algorithms, it is easy for the current cryptosystems to be broken since the algorithms can existentially solve the underlying mathematical problems such as integer factorization, discrete logarithm problem and elliptic curve problem, which formed the basis of the security of the affected cryptosystems. Based on this realization and as part of our readiness for a post quantum era, we explored other mathematical structures (lattices, hashes, codes, isogenies, high entropy-based symmetric key resistance, and multivariate quadratic problems) whose hardness could surpass the cryptanalytic nightmare posed by quantum computers and quantum-based algorithms. Our contribution is that, based on the findings of this research work, we can confidently assert that all hope is not lost for organizations heavily relying on protocols and applications like HTTPS, TLS, PGP, Bitcoin, etc., which derived their security from the endangered cryptosystems.

International Journal of Engineering and Advanced TechnologyJun 23, 202339 citations