The security of popular public key-cryptographic protocols, such as RSA, Diffie-Hellman key exchange and the Digital Signature Algorithm (DSA), is endangered by the advent of quantum computers. Shor brought a big breakthrough with his quantum algorithm that can be used to factor an arbitrarily large integer into the product of its prime factors, hence jeopardizing the security of RSA, and that at the same time also solves the Discrete Logarithm Problem, which raises issues for certain Diffie-Hellman based cryptosystems and digital signatures. It is hence crucial to upgrade our current tools for post-quantum cryptography: it should be infeasible, even using quantum algorithms, to break the new cryptosystems. Popular candidates include for example elliptic curve or lattice-based cryptography, but they share something in common: they are specific cases of the more general Hidden Subgroup and connected Hidden Shift Problem.
The security of popular public key-cryptographic protocols, such as RSA, Diffie-Hellman key exchange and the Digital Signature Algorithm (DSA), is endangered by the advent of quantum computers. Shor brought a big breakthrough with his quantum algorithm that can be used to factor an arbitrarily large integer into the product of its prime factors, hence jeopardizing the security of RSA, and that at the same time also solves the Discrete Logarithm Problem, which raises issues for certain Diffie-Hellman based cryptosystems and digital signatures. It is hence crucial to upgrade our current tools for post-quantum cryptography: it should be infeasible, even using quantum algorithms, to break the new cryptosystems. Popular candidates include for example elliptic curve or lattice-based cryptography, but they share something in common: they are specific cases of the more general Hidden Subgroup and connected Hidden Shift Problem.
Quantum cryptography is a promising field for securing information against quantum computers. Shor's algorithm, a quantum algorithm, can factor large prime numbers in polynomial time and solve the discrete logarithm problem, which is the basis for classical cryptographic algorithms like Rivest-Shamir-Adleman algorithm (RSA), Diffie-Hellman key exchange (DHKE), and Elliptic Curve Diffie-Hellman algorithm(ECDH). These algorithms pose a significant threat to their security and reliability. Post-quantum cryptography techniques are being implemented by all industries to address the threat posed by quantum supremacy. The chapter discusses the potential threat of Shor's algorithm on classical cryptographic algorithms and discusses post-quantum cryptographic algorithms like lattice-based, multivariate, code-based, and Hash-based cryptography. It also discusses recent advancements that have improved the security and usefulness of these algorithms.
Many cryptographic algorithms depend on computational complexity assumptions. Notorious cases are the RSA algorithm for public key criptography or the Diffie-Hellman key exchange protocol, to publicly agree on a common secret key. Both algorithms are known to be broken by quantum computing as well as those that can be reduced to a discrete logarithm problem. These are key algorithms in our digital society and are at the basis of everyday tasks, specially those that rely on digital signatures. The RSA algorithm, in particular, is probably the most used algorithm and is its assumed security the one that guards most of the e-commerce nowadays. In this case, it is the time complexity of finding the prime factors of a large number, that grows worse than polinomially with the size of the number, the main guardian of our cyberinfrastructure. The fact that a quantum computer can solve this problem in polynomial time using Shor's algorithm is seen as a potentially major disruption and has prompted security agencies to advice the progressive deprecation of these algorithms.
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.
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.
The advent of quantum computing poses a significant threat to the security of current asymmetric cryptographic systems, which underpin much of modern digital communication and security. These systems, predominantly RSA and Elliptic Curve Cryptography (ECC), rely on the computational hardness of mathematical problems such as integer factorization and the discrete logarithm problem. Shor's algorithm, a quantum algorithm, demonstrates the ability to efficiently solve these problems, rendering classical public-key cryptography vulnerable to attacks by sufficiently powerful quantum computers. This paper argues for and thoroughly examines the strategic imperative of transitioning from these classical cryptographic foundations to a new paradigm based on lattices, which are believed to be resistant to quantum attacks. We delve into the fundamental mathematical problems underlying lattice-based cryptography, such as the Shortest Vector Problem (SVP) and the Learning With Errors (LWE) problem, whose worst-case hardness is leveraged to achieve cryptographic security. A comprehensive literature review is provided, tracing the evolution of quantum threats and the emergence of lattice-based schemes. The methodology details the construction principles of prominent lattice-based cryptosystems. Results demonstrate their theoretical security against quantum adversaries and highlight their practical attributes, including compact key sizes and competitive performance. The discussion section contextualizes lattice-based cryptography within the broader landscape of post-quantum candidates, examining their strengths, weaknesses, and the ongoing standardization efforts by organizations like NIST. We conclude that lattice-based cryptography offers a robust and promising foundation for building resilient asymmetric cryptographic systems in the post-quantum era, ensuring the long-term security of digital information through a necessary re-architecture of cryptographic primitives.
Shor's shockingly fast quantum algorithm for solving the period-finding problem is a threat for the most common public-key primitives, as it can be efficiently applied to solve both the Integer Factorisation Problem and the Discrete Logarithm Problem. In other words, many once-secure protocols have to be replaced by still-secure alternatives. Instead of relying, for example, on the RSA protocol, the Diffie-Hellman key-exchange or the (Elliptic Curve) Digital Signature Algorithm, many researchers moved their attention to the design and analysis of primitives which are yet to be broken by quantum algorithms. The urgency of the threat imposed by quantum computers led the U.S. National Institute of Standards and Technology (NIST) to open calls for both Post-Quantum Public-Keys Exchange Algorithms and Post-Quantum Digital Signature Algorithms. In this brief survey we focus on the round 3 finalists and alternate candidates for Digital Signatures: CRYSTALS-DILITHIUM, FALCON, Rainbow, SPHINCS+, GeMSS, Picnic.