Computer security in a post-quantum world is a topic of great significance. The security of a vast number of public key encryption and key distribution techniques is dependent upon various number theoretic frameworks such as factoring, discrete logarithms and elliptic curves. Yet, variations on Shor’s algorithm have provided a theoretical basis for rendering such systems vulnerable to quantum attacks. In this work, we review quantum solutions for typical number theoretic problems. After leading up to elliptic curve systems, we highlight the relevance of computing modular inverses. Finally, refinements to quantum versions of the extended Euclidean algorithm are presented.
Computer security in a post-quantum world is a topic of great significance. The security of a vast number of public key encryption and key distribution techniques is dependent upon various number theoretic frameworks such as factoring, discrete logarithms and elliptic curves. Yet, variations on Shor’s algorithm have provided a theoretical basis for rendering such systems vulnerable to quantum attacks. In this work, we review quantum solutions for typical number theoretic problems. After leading up to elliptic curve systems, we highlight the relevance of computing modular inverses. Finally, refinements to quantum versions of the extended Euclidean algorithm are presented.
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.
The rise of the new paradigm (Quantum computing) in the recent years have created a major security challenge to classical and widely used primitive cryptography schemes such as ECC (Elliptic Curve Cryptography) and RSA (Rivest-Shamir-Adleman) Algorithm. These classical computing algorithms depend on the problems of discrete logarithm and integer factorization respectively. Recent advancements in quantum computing have made encryption schemes more vulnerable since they are weak to some quantum attacks, like Shor’s Algorithm and Grove’s Algorithm. Therefore the call for a new set of algorithms known as Post-Quantum cryptography (PQC) that would not be vulnerable to quantum attacks is imminent. NIST haven selected some candidates in the second round of Post-Quantum Cryptographic algorithms standardization project. This work’s goal is to review these algorithms under there types. A rigorous survey on each Post-Quantum Cryptography schemes and their underlying properties will be x-rayed while recommending areas for research in this new security paradigm.
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.
The impending arrival of large-scale quantum computers poses a significant threat to modern public-key cryptography, which is largely based on the hardness of integer factorization and the discrete logarithm problem. Elliptic Curve Cryptography (ECC), a cornerstone of current digital security, is particularly vulnerable to attacks by quantum algorithms, notably Shor's algorithm. This has catalyzed the development of Post-Quantum Cryptography (PQC), a new generation of cryptographic systems designed to be secure against both classical and quantum adversaries. Among the various PQC families, isogeny-based cryptography has emerged as a compelling, albeit complex, candidate. This paper explores the reimagination of elliptic curve principles for a post-quantum world through the lens of isogeny graphs. We provide a comprehensive overview of the transition from classical ECC to isogeny-based schemes, detailing the mathematical foundations of elliptic curve isogenies and the construction of supersingular isogeny graphs. The core of our analysis focuses on how the problem of finding a secret isogeny path between two curves in this graph forms the basis for quantum-resistant cryptographic protocols. We review the evolution of seminal protocols such as Supersingular Isogeny Diffie-Hellman (SIDH) and its variants, discussing their initial promise. Crucially, the paper also addresses the recent groundbreaking cryptanalytic attacks on SIDH, which have reshaped the landscape of isogeny-based cryptography. We analyze the implications of these attacks and the ongoing research to develop new, more secure isogeny-based schemes like SQISign. By comparing the performance metrics (key size, performance, security) of isogeny-based systems with other leading PQC candidates, such as those based on lattices and codes, this paper offers a balanced perspective on their potential role in future cryptographic standards.
We show in some detail how to implement Shor's efficient quantum algorithm for discrete logarithms for the particular case of elliptic curve groups. It turns out that for this problem a smaller quantum computer can solve problems further beyond current computing than for integer factorisation. A 160 bit elliptic curve cryptographic key could be broken on a quantum computer using around 1000 qubits while factoring the security-wise equivalent 1024 bit RSA modulus would require about 2000 qubits. In this paper we only consider elliptic curves over GF(p) and not yet the equally important ones over GF(2^n) or other finite fields. The main technical difficulty is to implement Euclid's gcd algorithm to compute multiplicative inverses modulo p. As the runtime of Euclid's algorithm depends on the input, one difficulty encountered is the ``quantum halting problem''.
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).