Research Trends in Quantum Computational Algorithms for Cryptanalysis

Aloy Anuja Mary G

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

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.

Romain Alléaume

Travis L. Scholten, Carl J. Williams, Dustin Moody +5 more

Quantum computing is an emerging technology with potentially far-reaching implications for national prosperity and security. Understanding the timeframes over which economic benefits and national security risks may manifest themselves is vital for ensuring the prudent development of this technology. To inform security experts and policy decision makers on this matter, we review what is currently known on the potential uses and risks of quantum computers, leveraging current research literature. The maturity of currently-available quantum computers is not yet at a level such that they can be used in production for large-scale, industrially-relevant problems, and they are not believed to currently pose security risks. We identify 2 large-scale trends -- new approximate methods (variational algorithms, error mitigation, and circuit knitting) and the commercial exploration of business-relevant quantum applications -- which, together, may enable useful and practical quantum computing in the near future. Crucially, these methods do not appear likely to change the required resources for cryptanalysis on currently-used cryptosystems. From an analysis we perform of the current and known algorithms for cryptanalysis, we find they require circuits of a size exceeding those that can be run by current and near-future quantum computers (and which will require error correction), though we acknowledge improvements in quantum algorithms for these problems are taking place in the literature. In addition, the risk to cybersecurity can be well-managed by the migration to new, quantum-safe cryptographic protocols, which we survey and discuss. Given the above, we conclude there is a credible expectation that quantum computers will be capable of performing computations which are economically-impactful before they will be capable of performing ones which are cryptographically-relevant.

Takenobu Seitou

Alexei Petrenko, Sergei Petrenko

Purpose of the article: development of quantum algorithms for efficient solution of cryptanalysis problems of asymmetric encryption schemes (RSA, ElGamal) and digital signature (DSA, ECDSA or RSA-PSS), based on computationally difficult problems of factorization and discrete logarithm.Research methods: Methods of quantum cryptanalysis based on the algorithms of Shor, Grover, Simon, etc.Results: algorithms for solving problems of quantum cryptanalysis of two-key cryptography schemes in polynomial time.Practical relevance: consists in developing a solution for computationally difficult problems of factorization and discrete logarithm in polynomial time, taking into account the security of the discrete algorithm (DLP) and the discrete elliptic curve algorithm (ECDLP). The obtained scientific results formed the basis for the development of a special Software Development Kit, SDK for cryptanalysis “Kvant-K”. The Certificate of state registration of the computer program No. 2020665981 was received.