This paper deals with alternative cryptosystems which resist the attacks of quantum computers. The work is divided into 3 chapters. In the first chapter we give the motivation to observe such systems. We explain some basic concepts from cryptography and point out some key features that make a given cryptosystem good. Then we give a short introduction to quantum computing, explaining the difference between a classical and a quantum computer, in addition to showing how computation works in a quantum environment. For the end of the first chapter we briefly explain the most important quantum algorithm: Shor’s algorithm. Shor’s algorithm allows us to easily factorize numbers and thus break most of the cryptosystems used today. For this reason, there is a need for cryptosystems based on a different class of problems. In the second chapter we present the first class of such problems, the problems defined over lattices, and we explain an example of a cryptosystem based on these problems, the GGH cryptosystem with a public key. At the beginning this chapter, we define lattices and show some key features. Then we describe most of the major problems on lattices such as SVP and CVP. To conclude, we define the GGH cryptosystem, explain how it works and what are the drawbacks and advantages. In the last, third chapter, we present another class of problems that are currently resisting quantum attacks, code based problems. First we explain what the codes are and using an example code explain their essential properties. The most important of all these features is the ability to correct errors and precisely around this feature has Mceliece designed his cryptosystem. At the end of the chapter, we explain the idea of the Mceliece cryptosystem and comment on its quality for practical application.
This paper deals with alternative cryptosystems which resist the attacks of quantum computers. The work is divided into 3 chapters. In the first chapter we give the motivation to observe such systems. We explain some basic concepts from cryptography and point out some key features that make a given cryptosystem good. Then we give a short introduction to quantum computing, explaining the difference between a classical and a quantum computer, in addition to showing how computation works in a quantum environment. For the end of the first chapter we briefly explain the most important quantum algorithm: Shor’s algorithm. Shor’s algorithm allows us to easily factorize numbers and thus break most of the cryptosystems used today. For this reason, there is a need for cryptosystems based on a different class of problems. In the second chapter we present the first class of such problems, the problems defined over lattices, and we explain an example of a cryptosystem based on these problems, the GGH cryptosystem with a public key. At the beginning this chapter, we define lattices and show some key features. Then we describe most of the major problems on lattices such as SVP and CVP. To conclude, we define the GGH cryptosystem, explain how it works and what are the drawbacks and advantages. In the last, third chapter, we present another class of problems that are currently resisting quantum attacks, code based problems. First we explain what the codes are and using an example code explain their essential properties. The most important of all these features is the ability to correct errors and precisely around this feature has Mceliece designed his cryptosystem. At the end of the chapter, we explain the idea of the Mceliece cryptosystem and comment on its quality for practical application.
The aim of this thesis is to study quantum computers and their impact on public-key cryptography. Crucial part of the work is dedicated to theoretical basis and definitions necessary for understanding the basic principles of quantum computers. The further chapters describe Shor's algorithm, explain the part of integer factoring problem in the security of current public key cryptographic algorithms, and show how to break the most widely used assymetric algorithm RSA by means of effective factoring. Last chapter provides comparison of classical factoring algorithms with Shors algorithm, mentions cryptography resistant to quantum computer attacks and discusses the current state of development in the field of qunatum computing. The conclusion summarizes both potential and real impact of quantum computers on public-key cryptography.
The boom of quantum computing has brought both benefits and threats to cyber-physical systems. The primary purpose of the paper is to highlight the possible threats by quantum computers, and to provide a comparative study of the on-going quantum-resistant post-quantum cryptography suitable for current network infrastructure. Asymmetric key cryptography, mainly the widely adopted RSA and ECC algorithms, has been compromised by quantum algorithms such as the Shor’s algorithm. Moreover, symmetric algorithms such as AES are weakened by brute force attacks using Grover’s algorithm. Thus, researchers are developing public key algorithms based on hard mathematical models that provide resistance against quantum attacks and can be deployed in classical hardware. We categorize the well-known post-quantum schemes based on (1) their security goals: confidentiality and integrity, and (2) their mathematical problems: code-based, lattice-based, super-singular elliptic curve isogeny based, multivariate and hash-based algorithm. Hash-based post- quantum cryptography is further categorized into two: stateless and stateful signature scheme. Furthermore, the chapter compares the algorithms based on the key sizes, ciphertext sizes, signature sizes, computation, and time cost. The paper also presents the challenges faced by the post-quantum algorithms, and it outlines directions for further research to improve the algorithms. Moreover, various cyber-physical fields, including industrial control systems, mainly nuclear power plants, water management plants, and even space stations and their infrastructure, rely on classical cryptography. Thus, the paper presents a generic hybrid cryptosystem based on classical and post-quantum cryptography to enhance resistance against classical and quantum attacks.
This chapter introduces lattice-based cryptography, a critical mathematical framework for securing communications in the post-quantum era. While classical public-key cryptosystems rely on the intractability of integer factorization and discrete logarithms, these foundations are fundamentally vulnerable to quantum computing threats, specifically Shor's algorithm. To address this vulnerability, the text explores cryptosystems built upon the algebraic structure of lattices, defined as discrete points in n-dimensional Euclidean space generated by linearly independent vectors. The chapter systematically covers the mathematical properties of lattices, associated computational problems, and distance metrics. It provides an in-depth examination of lattice basis reduction algorithms, which are fundamental to both the design and security evaluation of these systems. Furthermore, the chapter details the operational mechanics—including encryption, decryption, and cryptanalysis—of prominent post-quantum architectures, specifically the GGH and NTRU public-key cryptosystems. By transitioning from classical number theory to high-dimensional geometry, this chapter equips readers with the cryptographic primitives necessary to withstand future quantum attacks.
It is known that the development of quantum computers will break the cryptographic schemes that are in use today. Since Shor’s algorithm is able to solve the factoring and discrete logarithm problems, all cryptographic systems based on these two problems will get broken in the presence of large-scale quantum computers. Lattice-based schemes, however, are considered secure against attacks with these new machines. In this paper we present an overview of lattice-based cryptosystems, showing the most recent and the most promising candidates for encryption and signatures based on lattice problems. We explain the advantages and disadvantages of the cryptographic schemes. We also adjoin details about zero knowledge identification. With this work we try to give insight to one of the most promising candidates of future cryptography, for the time when potential quantum computers exist. We also point out drawbacks of these systems, which discloses directions for future work in lattice-based cryptography.
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.
Quantum computing threatens current public-key cryptographic systems, necessitating a transition to quantum-resistant alternatives. This paper analyzes how Shor's algorithm enables quantum computers to efficiently break RSA and Elliptic Curve Cryptography by solving their underlying mathematical problems, demonstrating these systems cannot be salvaged through parameter increases. We evaluate lattice-based cryptography as a post-quantum solution, examining its foundation on high-dimensional lattice problems such as the Shortest Vector Problem and Learning With Errors. Through analysis of NIST-standardized algorithms CRYSTALS-Kyber and CRYSTALS-Dilithium, we assess the security assumptions, computational efficiency, and implementation considerations of lattice-based schemes. Our findings reveal that while quantum computing poses an existential threat to current cryptographic infrastructure, lattice-based cryptography provides a viable quantum-resistant alternative with strong security guarantees and practical performance characteristics.