River Publishers eBooks

Applied Quantum Cryptanalysis

Alexei Petrenko

Published Feb 7, 2023• 8 citations

Abstract

Today we witness an explosive growth in attention to Q-computing. Q-computing technologies, along with artificial intelligence (AI) and machine learning (ML) technologies, cloud and foggy computing, as well as technologies for collecting and streaming processing of Big Data and ETL, are constantly leading the lists of ""end-to-end"" information technologies for the digital economy of technologically developed countries of the world. One of the main reasons for this is the potential ability of quantum computers to solve some computational problems more efficiently than any of the most modern classical computers of the von Neumann architecture (supercomputers). The most expressive and interesting, from an applied point of view, examples of such problems are integer factorization, effectively performed by Shor's quantum algorithm, as well as record search in an unordered database, effectively solved by Grover's algorithm. This monograph contains the best practice for solving problems of quantum cryptanalysis to improve cyber security and resilience of the digital economy. The book discusses well-known and author's software implementations of promising quantum Shor algorithms, Grover, Simon et al. Shor's algorithm provides exponential acceleration of solving factorization problems, discrete logarithm problems (DLPs) and elliptic curve discrete logarithm problems (ECDLPs). The mentioned tasks are widely used in TLS, SSH or IPsec cryptographic applications of Internet/Intranet and IIoT/IoT networks, communication protocols based on Diffie–Hellman key agreements (dependent on the strength of the DLP or ECDLP), digital signature algorithms (DSA, ECDSA, RSA-PSS), public key encryption algorithms (El Gamal, RSA-OAEP), etc. In other words, Shor's quantum algorithm is potentially capable of violating these algorithms, and with them all the mechanisms of public-key cryptography deployed in cyberspace.

DOI: 10.1201/9781003392873

Related papers

Introduction

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.

River Publishers eBooksFeb 7, 20230 citations

Basic Algorithms Quantum Cryptanalysis

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.

Voprosy kiberbezopasnostiJan 1, 20237 citations

Post–Quantum Cryptography – A Primer

P. V. Ananda Mohana

Traditionally, information security needed encryption, authentication, key management, non-repudiation and authorization which were being met using several techniques. Standardization of algorithms by National Institute of Standards and Technology (NIST) has facilitated international communication for banking and information transfer using these standards. Encryption can be carried out using Advanced Encryption Standard (AES) using variable block lengths (128, 192 or 256 bits) and variable key lengths (128, 192 or 256 bits). Solutions for light weight applications such as those for Internet of Things (IoT) are also being standardized. Message integrity is possible using host of hash algorithms such as SHA-1, SHA-2 etc., and more recently using SHA-3 algorithm. Authentication is possible using well known Rivest-Shamir-Adleman (RSA) algorithm needing 2048/4096 bit operations. Elliptic Curve Cryptography (ECC) is also quite popular and used in several practical systems such as WhatsApp, Blackberry etc. Key exchange is possible using Diffie-Hellman algorithm and its variations. Digital Signatures can be carried out using RSA algorithm or Elliptic Curve Digital Signature Algorithm (ECDSA) or DSA (Digital Signature Algorithm). All these algorithms derive security from difficulty in solving some mathematical problems such as factorization problem or discrete logarithm problem. Though published literature gives evidence of solving factorization problem upto 768 bits only, it is believed that using Quantum computers, these problems could be solved by the end of this decade. This is due to availability of the pioneering work of Shor and Grover [1]. For factoring an integer of N bits, Shor’s algorithm takes quantum gates. As such, there is ever growing interest in being ready for the next decade with algorithms that may resist attacks in the quantum computer era. NIST has foreseen this need and has invited proposals from researchers all over the world. In the first round, about 66 submissions were received which have been scrutinized for completeness of submissions , novelty of the approach and security and 25 of these were promote to second round to improve based on the comments received on the first round submission. These will be analyzed for security and some will be selected for final recommendation for use by industry. These are for encryption/decryption, key agreement, hashing and Digital Signatures for both hardware and software implementations. In this paper, we present a brief survey of the state of the art in post-Quantum Cryptography (PQC) followed by study of one of technique referred to as Learning With Errors (LWE) in some detail.

Mar 31, 20200 citations

The Relevance of Quantum Cryptanalysis

Alexei Petrenko, Sergei Petrenko

This chapter shows the relevance of solving practical issues of quantum cryptanalysis to ensure the required cybersecurity digital economy. It presents the analysis of the well-known national quantum initiatives and programs in technologically advanced countries of the world. The chapter also shows the role and place of applied quantum cryptanalysis in modern cryptology search studies. It reveals the main prerequisites and scientific foundations for solving practical problems of quantum cryptanalysis based on the algorithms of Shor , Grover , Simon , etc. The chapter explains the potential vulnerabilities of modern blockchain systems to typical quantum crypto attacks. It defines the basic requirements for promising methods, algorithms, and software of quantum cryptanalysis. An effective quantum attack will be to search for the private key when the public key is revealed after the broadcast of the signed transaction to the network. This allows an attacker to sign a new transaction using a private key, posing as the key owner.

River Publishers eBooksFeb 7, 20230 citations

Post-Quantum Cryptography for Secure Communication: A Systematic Review of Algorithms, Performance Trade-offs, and Emerging Challenges

Suvhodip Saha

The rapid growth of quantum computing poses a critical threat to classical cryptographic systems. That is due in large part to the fact that they represent efficient solutions for some of the most challenging mathematical problems such as integer factoring or finding discrete logarithms. Schemes currently in wide use including RSA, Diffie–Hellman, and elliptic curve cryptography are particularly susceptible to being attacked by quantum computers, using algorithms like Shor's Algorithm and Grover's Algorithm. The advent of post-quantum cryptography (PQC) provides a promising potential answer to providing longterm security from adversaries using quantum computing capabilities. This paper presents a comprehensive state-of-the-art review of various PQC techniques currently being researched, including lattice-based methods, code-based methods, multivariate methods, hash-based methods, and isogeny-based methods. key challenges that will need to be addressed include computational overhead, large key sizes and implementation complexity. Furthermore the study reviews the current standardization efforts by the National Institute of Standards and Technology related to PQC and discusses some of the very specific practical considerations that need to be considered before widely deploying these techniques. The paper concludes by a complete list of existing research challenges and proposed future work that will assist in the development of efficient and scalable systems that will resist attacks from quantum computers.

International Journal for Research in Applied Science and Engineering TechnologyMar 24, 20260 citations

A Comprehensive Review of Post-Quantum Cryptography Algorithms

Samandeep Kaur, Jaswinder Singh

The development of quantum computing has been rapid, and an existential threat to computational hardness assumptions that underlie today's public-key cryptography has been encountered. This manuscript is a complete and thoroughly organized review of Post-Quantum Cryptography (PQC), discussing the mathematical concepts, complexity, and mechanisms of the algorithms that underpin quantum-safe security infrastructures. Rather than the principles of quantum mechanics, the analysis mathematically defines the basic principles of qubits, superposition, and entanglement, and clarifies common misunderstandings of the theory of parallelism in quantum mechanics. The research places cryptographic problems into the Bounded-Error Quantum Polynomial-Time (BQP) complexity class, thus highlighting the exact defects of classical algorithms. The quantum gate complexity of Shor's algorithm is compared to classical bounds as in Pollard's rho algorithm for the Elliptic Curve Discrete Logarithm Problem (ECDLP), for a detailed comparative cryptanalysis. The comparison highlights a very important “quantum security inversion” in that Elliptic Curve Cryptography (ECC) is much more susceptible to the early-stage fault-tolerant quantum computer as compared to the approach used today in RSA. It unfolds the architectural dependency of quantum algorithms, one by one, from the Quantum Fourier Transform (QFT) to Quantum Phase Estimation (QPE) and Shor's algorithm to Grover's algorithm. Last but not least, the manuscript examines emerging attack primitives such as lattice-based, code-based, and hash-based cryptography, their security models, side channel vulnerabilities, and the recently finalised Federal Information Processing Standards (FIPS 205, 203, and 204) that have been published by the National Institute of Standards and Technology (NIST).

Journal of Computer ScienceSep 1, 20260 citations