Abstract In typical well-known cryptosystem, the hardness of classical problems plays a fundamental role in ensuring its security. While, with the booming of quantum computation, some classical hard problems tend to be vulnerable when confronted with the already-known quantum attacks, as a result, it is necessary to develop the post-quantum cryptosystem to resist the quantum attacks. With the purpose to bridge the two disciplines, it is significant to summarize known quantum algorithms and their threats toward these cryptographic intractable problems from a perspective of cryptanalysis. In this paper, we discussed the designing methodology, algorithm framework and latest progress of the mathematic hard problems on which the typical cryptosystems depend, including integer factorization problem, discrete logarithmic problem and its variants, lattice problem, dihedral hidden subgroup problems and extrapolated dihedral coset problem. It illustrated the reason why some cryptosystems such as RSA and ECC are not resistant to quantum attacks, yet some of them like lattice cryptosystems remain intact facing quantum attacks.
Abstract In typical well-known cryptosystem, the hardness of classical problems plays a fundamental role in ensuring its security. While, with the booming of quantum computation, some classical hard problems tend to be vulnerable when confronted with the already-known quantum attacks, as a result, it is necessary to develop the post-quantum cryptosystem to resist the quantum attacks. With the purpose to bridge the two disciplines, it is significant to summarize known quantum algorithms and their threats toward these cryptographic intractable problems from a perspective of cryptanalysis. In this paper, we discussed the designing methodology, algorithm framework and latest progress of the mathematic hard problems on which the typical cryptosystems depend, including integer factorization problem, discrete logarithmic problem and its variants, lattice problem, dihedral hidden subgroup problems and extrapolated dihedral coset problem. It illustrated the reason why some cryptosystems such as RSA and ECC are not resistant to quantum attacks, yet some of them like lattice cryptosystems remain intact facing quantum attacks.
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.
Modern public key cryptosystems rely on two assumptions regarding computational difficulty: the integer factorization problem (RSA) and the discrete logarithm problem (elliptic curve cryptography).These problems have stood the test of time for four decades of cryptanalysis.Yet, their algebraic and periodic nature makes them vulnerable to quantum algorithms, most notably Shor's algorithm (1994).This paper presents a detailed comparison between classical and quantum-resistant cryptographic systems with an emphasis on lattice-based systems.The Learning With Errors (LWE) problem and its variants (Ring-LWE, Module-LWE) do not have the same periodicity that makes problems like integer factorization and discrete logarithms susceptible to quantum algorithms.Furthermore, LWE problems have reductions from worst-case lattice problems and have mathematical proofs of quantum resistance.Due to the vulnerability of ECDSA algorithms for cryptocurrencies, it is estimated that current cryptocurrencies will no longer be secure once quantum computer technology matures within the next 10-30 years, potentially compromising holdings estimated at between $260 billion and $390 billion as of August 2026.The implications of cryptanalysis on public key cryptography systems motivate mathematical recommendations regarding the security of current cryptosystems and the need for a shift to post-quantum cryptographic standards.
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.
As the development of quantum computing systems advances, the integrity of current public-key and symmetrickey cryptographic systems, such as RSA, ECC, and AES, faces unprecedented threats.These systems rely on mathematical problems like integer factorization and discrete logarithms, which quantum algorithms like Shor's can solve exponentially faster than classical ones.This review examines the vulnerability of widely used cryptographic systems and evaluates how close quantum hardware is to breaching real-world encryption.It also discusses the development of post-quantum cryptographic algorithms, specifically lattice-based, code-based, and multivariate polynomial systems designed to resist quantum attacks.This paper will also assess the strengths, limitations, and standardization progress of these post-quantum solutions to provide an understanding of the modern cryptographic landscape.
The landscape of modern cryptography is fundamentally challenged by the advent of quantum computing. Current public-key cryptosystems, which form the bedrock of secure digital communication, rely on the computational hardness of problems such as integer factorization (RSA) and the discrete logarithm problem (ECC). However, Shor's algorithm, if implemented on a sufficiently powerful quantum computer, can efficiently break these schemes, rendering them insecure. This paper explores the critical transition from these classical number theory problems to lattice-based cryptography, presenting a comprehensive analysis of the motivations, theoretical underpinnings, and practical implications for forging post-quantum cryptographic security. We delve into the mathematical foundations of lattice problems, such as the Shortest Vector Problem (SVP) and Learning With Errors (LWE), which are believed to resist known quantum algorithms. Through a thorough literature review, we trace the evolution of cryptographic thought, detailing the vulnerabilities of pre-quantum schemes and the emergence of lattice-based constructions as leading candidates for post-quantum standardization. The methodology outlines a comparative theoretical analysis of security, efficiency, and robustness against both classical and quantum attacks. Results demonstrate the compelling advantages of lattice-based schemes in terms of provable security reductions and resistance to quantum threats, albeit with considerations for increased key and ciphertext sizes. The discussion highlights the challenges and opportunities in the deployment and standardization of these new cryptographic primitives, emphasizing their critical role in securing future digital infrastructures. This work concludes that lattice-based cryptography offers a robust and theoretically sound pathway to establishing enduring security in a quantum-threatened world.
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.