Powerful new computers based on the principles of quantum mechanics could crack the codes that safeguard our information today. The National Institute of Standards and Technology is running a competition to find more secure encryption methods to address this future challenge. CRYSTALS-Kyber is a messaging scramble Algorithm built with a complex structure called a lattice. This design is considered secure against powerful quantum computers because there is no known shortcut for them to break the code efficiently, unlike some other classical encryption Algorithms. In this paper, we introduce primitive information about quantum characteristics, computation, and main gate circuits, as well as the quantum theories for the design of post-quantum cryptosystems. Then, we listed the main key players in the quantum field and their achievements. We also compared the programming platforms used in developing programs in a quantum environment. Finally, we focused on cryptography applications and showed some of the mathematics background required to build knowledge for post-quantum cryptography algorithms, especially the CRYSTALS-Kyber algorithms and its core block Number Theoretic Transformation (NTT).
Powerful new computers based on the principles of quantum mechanics could crack the codes that safeguard our information today. The National Institute of Standards and Technology is running a competition to find more secure encryption methods to address this future challenge. CRYSTALS-Kyber is a messaging scramble Algorithm built with a complex structure called a lattice. This design is considered secure against powerful quantum computers because there is no known shortcut for them to break the code efficiently, unlike some other classical encryption Algorithms. In this paper, we introduce primitive information about quantum characteristics, computation, and main gate circuits, as well as the quantum theories for the design of post-quantum cryptosystems. Then, we listed the main key players in the quantum field and their achievements. We also compared the programming platforms used in developing programs in a quantum environment. Finally, we focused on cryptography applications and showed some of the mathematics background required to build knowledge for post-quantum cryptography algorithms, especially the CRYSTALS-Kyber algorithms and its core block Number Theoretic Transformation (NTT).
Abstract Quantum computing poses a significant threat to the security of many current cryptographic algorithms. This imminent risk has accelerated the development and standardization of new cryptosystems, known as post-quantum cryptosystems. These cryptosystems are designed to protect digital information in the quantum era using classical computing resources. CRYSTALS-Kyber is a lattice-based post-quantum encryption scheme that has been selected as a standard by the National Institute of Standards and Technology. This work presents a novel kleptographic attack against the CRYSTALS-Kyber scheme, providing both theoretical insights and practical results that demonstrate its feasibility. One conclusion is that this post-quantum cryptosystem may be vulnerable to kleptographic backdoors. As a result, this study offers a mathematical analysis, software implementations, and practical methodologies to detect such backdoors, thereby contributing to the development of more transparent and verifiable cryptographic standards.
Cryptography is very essential in our daily life, not only for confidentiality of information, but also for information integrity verification, non-repudiation, authentication, and other aspects. In modern society, cryptography is widely used; everything from personal life to national security is inseparable from it. With the emergence of quantum computing, traditional encryption methods are at risk of being cracked. People are beginning to explore methods for defending against quantum computer attacks. Among the methods currently developed, quantum key distribution is a technology that uses the principles of quantum mechanics to distribute keys. Post-quantum encryption algorithms are encryption methods that rely on mathematical challenges that quantum computers cannot solve quickly to ensure security. In this study, an integrated review of post-quantum encryption algorithms is conducted from the perspective of traditional cryptography. First, the concept and development background of post-quantum encryption are introduced. Then, the post-quantum encryption algorithm Kyber is studied. Finally, the achievements, difficulties and outstanding problems in this emerging field are summarized, and some predictions for the future are made.
The emergence of quantum computers threatens current cryptographic systems, and NIST is preparing for the post-quantum era through the post-quantum cryptography (PQC) contest. CRYSTALS-Kyber is a lattice-based cipher suite that is used as a PQC standard. Lattice-based cryptography is considered quantum-safe for quantum computing because a quantum algorithm that can more efficiently solve the lattice problem of lattice-based cryptography compared to a classic algorithm has not been reported as yet. In this paper, we present quantum circuits tailored to NTT and inverse NTT, employed for optimized polynomial multiplication within CRYSTALS-Kyber. The proposed quantum circuits operate at Z3329[X]/(X256+1), which are the parameters of CRYSTALS-Kyber. We provide an in-depth description of the NTT/InvNTT quantum circuit’s operation and subsequently assess and analyze the quantum resources necessary for these functions. The NTT/InvNTT quantum circuits comprise four unique sub-functions, with the InvNTT additionally incorporating Barrett reduction. To the best of our knowledge, this represents the inaugural implementation of the CRYSTALS-Kyber NTT/InvNTT quantum circuits. We anticipate that our findings will aid in analyzing the security strengths of quantum computers for lattice-based cryptography.
The rapid progress of quantum computing is changing the assumptions on which many modern security systems are built. Public-key methods such as RSA and Elliptic Curve Cryptography (ECC) remain dependable against conventional computers, yet their underlying mathematical problems can be solved efficiently by a sufficiently capable quantum computer using algorithms such as Shor's algorithm. This creates a practical need to evaluate cryptographic techniques that can continue to protect information in a post-quantum environment. This study compares representative classical algorithms - RSA, ECC, and the Advanced Encryption Standard (AES) - with post-quantum approaches, with particular attention to CRYSTALS-Kyber and CRYSTALS-Dilithium. The comparison considers security assumptions, key-generation cost, encryption and decryption time, key size, memory demand, and resistance to quantum attacks. The reported benchmark values indicate that RSA has the highest processing cost among the evaluated schemes, whereas CRYSTALS-Kyber provides comparatively fast key generation, encryption, and decryption while maintaining resistance to known quantum attacks. The study also discusses a hybrid migration model in which established classical mechanisms and post-quantum algorithms operate together during the transition period. Overall, the findings support a gradual move toward quantum-resistant communication systems while recognising the deployment and storage overhead introduced by larger post-quantum keys.
The advent of quantum computing will pose a substantial threat to the security of classical cryptographic methods, which could become vulnerable to quantum-based attacks. In response to this impending challenge, the field of post-quantum cryptography has emerged, aiming to develop algorithms that can withstand the computational power of quantum computers. This study addressed the pressing concern of classical cryptographic methods becoming vulnerable to quantum-based attacks due to the rise of quantum computing. The emergence of post-quantum cryptography has led to the development of new resistant algorithms. Our research focused on four quantum-resistant algorithms endorsed by America’s National Institute of Standards and Technology (NIST) in 2022: CRYSTALS-Kyber, CRYSTALS-Dilithium, FALCON, and SPHINCS+. This study evaluated the security, performance, and comparative attributes of the four algorithms, considering factors such as key size, encryption/decryption speed, and complexity. Comparative analyses against each other and existing quantum-resistant algorithms provided insights into the strengths and weaknesses of each program. This research explored potential applications and future directions in the realm of quantum-resistant cryptography. Our findings concluded that the NIST algorithms were substantially more effective and efficient compared to classical cryptographic algorithms. Ultimately, this work underscored the need to adapt cryptographic techniques in the face of advancing quantum computing capabilities, offering valuable insights for researchers and practitioners in the field. Implementing NIST-endorsed quantum-resistant algorithms substantially reduced the vulnerability of cryptographic systems to quantum-based attacks compared to classical cryptographic methods.
In 1994, P. Shor discovered quantum algorithms that can break both the RSA cryptosystem and the ElGamal cryptosystem. In 2007, a Canadian company D-Wave demonstrated the first quantum computer. These events and quick further developments have brought a crisis to secret communication. In 2022, the National Institute of Standards and Technology (NIST) announced 4 candidates-CRYSTALS-Kyber, CRYSTALS-Dilithium, Falcon, and Sphincs+-for post-quantum cryptography standards. The first 3 are based on lattice theory and the last on Hash functions. In 2024, NIST announced 3 standards: FIPS 203 based on CRYSTALS-Kyber, FIPS 204 based on CRYSTALS-Dilithium, and FIPS 205 based on Sphincs+. The fourth standard based on Falcon is on the way. It is well known that the security of the lattice-based cryptosystems relies on the hardness of the shortest vector problem (SVP), the closest vector problem (CVP), and their generalizations. In fact, the SVP is a ball packing problem and the CVP is a ball covering problem. Furthermore, both SVP and CVP are equivalent to arithmetic problems for positive definite quadratic forms. There are several books and survey papers dealing with the computational complexity of the lattice-based cryptography for classical computers. However, there is no review article to demonstrate the mathematical foundation of the complexity theory. This paper will briefly introduce post-quantum cryptography and demonstrate its mathematical roots in ball packing, ball covering, and positive definite quadratic forms.