The development of quantum computers has led to the possibility of solving problems intractable to deal with in clas-sical computers. That threatens the current standard of public-key cryptography based on factoring or discrete-log problem. As a result, it is necessary to use a secure cryptosystem even in a quantum computing environment. NIST has been conducting a Post-Quantum Cryptography (PQC) standardization process. Recently, there have been attempting to design binary MQ solver with the Grover's algorithm to solve the binary Multivariate Quadratic (MQ) problem. However, most PQC candidates based on the MQ problem do not select a small security parameter and are over GF(16) and above. In this paper, we design the Grover's oracle circuit to solve the MQ problem over GF(31) that can be used to analyze the quantum security of PQC candidates such as Rainbow and MQDSS.
The development of quantum computers has led to the possibility of solving problems intractable to deal with in clas-sical computers. That threatens the current standard of public-key cryptography based on factoring or discrete-log problem. As a result, it is necessary to use a secure cryptosystem even in a quantum computing environment. NIST has been conducting a Post-Quantum Cryptography (PQC) standardization process. Recently, there have been attempting to design binary MQ solver with the Grover's algorithm to solve the binary Multivariate Quadratic (MQ) problem. However, most PQC candidates based on the MQ problem do not select a small security parameter and are over GF(16) and above. In this paper, we design the Grover's oracle circuit to solve the MQ problem over GF(31) that can be used to analyze the quantum security of PQC candidates such as Rainbow and MQDSS.
Much of the assumed safety and security of classical cryptographic building blocks depends on the hardness of number-theoretical problems. However, Shor's algorithm proves that conventional cryptographic systems are no longer secure under quantum systems. As a response to this challenge, researchers started to develop a new cryptographic method known as post-quantum cryptography (PQC), which is based on hard computational problem that can resist the quantum threats. The multivariate public-key cryptography (MPKC) is one such candidate. The theoretical security of MPKC comes from the intractability of the MQ problem, which is believed to be NP-hard. Herein, we analyze the security of MQDSS signature scheme proposed by Chen et al. We investigate the proof of security of MQDSS, assuming that the malicious party can access to the quantum resources. We demonstrate that in its current state, MQDSS has quite a few insecurities in the quantum setting. In response to the proposed threats, we pitch possible modifications to MQDSS. We emphasize that our proposed security threats do not restrict themselves to MQDSS, and can be extended to other MPKC and PQC based cryptographic primitives.
The security of current public-key cryptosystems relies on the hardness of factoring large integers or solving discrete logarithm problems. However, these mathematical problems can be solved in polynomial time using a quantum computer. This vulnerability has prompted research into post-quantum cryptography using alternative mathematical problems that are secure in the era of quantum computers. In this regard, the National Institute of Standards and Technology (NIST) began to standardize post-quantum cryptography in 2016. In this expository article, we give an overview of recent research on post-quantum cryptography. In particular, we describe the construction and security of multivariate polynomial cryptosystems and lattice-based cryptosystems, which are the main candidates of post-quantum cryptography.
In August 2015 the cryptographic world was shaken by a sudden and surprising announcement by the US National Security Agency NSA concerning plans to transition to post-quantum algorithms. Since this announcement post-quantum cryptography has become a topic of primary interest for several standardization bodies. The transition from the currently deployed public-key algorithms to post-quantum algorithms has been found to be challenging in many aspects. In particular the problem of evaluating the quantum-bit security of such post-quantum cryptosystems remains vastly open. Of course this question is of primarily concern in the process of standardizing the post-quantum cryptosystems. In this paper we consider the quantum security of the problem of solving a system of {\it m Boolean multivariate quadratic equations in n variables} (\MQb); a central problem in post-quantum cryptography. When n=m, under a natural algebraic assumption, we present a Las-Vegas quantum algorithm solving \MQb{} that requires the evaluation of, on average, O(20.462n) quantum gates. To our knowledge this is the fastest algorithm for solving \MQb{}.
In August 2015 the cryptographic world was shaken by a sudden and surprising announcement by the US National Security Agency NSA concerning plans to transition to post-quantum algorithms. Since this announcement post-quantum cryptography has become a topic of primary interest for several standardization bodies. The transition from the currently deployed public-key algorithms to post-quantum algorithms has been found to be challenging in many aspects. In particular the problem of evaluating the quantum-bit security of such post-quantum cryptosystems remains vastly open. Of course this question is of primarily concern in the process of standardizing the post-quantum cryptosystems. In this paper we consider the quantum security of the problem of solving a system of {\it m Boolean multivariate quadratic equations in n variables} (\MQb); a central problem in post-quantum cryptography. When n=m, under a natural algebraic assumption, we present a Las-Vegas quantum algorithm solving \MQb{} that requires the evaluation of, on average, O(20.462n) quantum gates. To our knowledge this is the fastest algorithm for solving \MQb{}.
Abstract It is viewed as revolutionary technology, offering incredible potential in terms of computing power within different scientific and industrial sectors. Quantum computers provide remarkable computing power; however, they also present significant security risks to existing public-key cryptography systems used to secure digital communication, online banking systems, government, medical applications, cloud computing systems, and IoT systems. Security of commonly used encryption schemes like RSA, DH, and ECC depends on mathematical problems that are impossible for classical computers to solve but can be easily resolved with the help of powerful enough quantum computers by using Shor’s algorithm. Furthermore, Grover’s algorithm makes exhaustive search attacks much faster, thus effectively lowering the security level of symmetric encryption schemes since it provides the speed-up for brute-force attacks. Post-Quantum Cryptography (PQC) turned out to be an effective and scalable method to protect digital data from attacks using quantum computing. In contrast to quantum cryptography, which requires a special quantum communication channel, PQC uses classical cryptographic algorithms that cannot be broken down by either classical or quantum computer due to certain mathematical problems. This research paper offers an extensive exploration of post-quantum cryptography through the analysis of the development of quantum computing, weaknesses of current cryptographic techniques, and mathematics behind quantum-resistant algorithms. Moreover, this paper explores the major classes of PQC techniques such as lattice-based, code-based, hash-based, multivariate, and isogeny-based cryptography and provides details about their security and application. Moreover, the report gives an overview of the NIST Post-Quantum Cryptography Standardization Project and analyzes recent standardizations of quantum-proof algorithms to be utilized in future digital infrastructures. Keywords: Post-Quantum Encryption, Quantum Security, Quantum-Proof Public-Key Cryptography, Lattice-Based Security Protocols, ML-KEM Key Encapsulation Mechanism, ML-DSA Digital Signature Algorithm, NIST Post-Quantum Cryptography, Contemporary Cybersecurity, Secure Communications, Cryptographic Algorithms.
The development of large quantum computers will have dire consequences for cryptography. Most of the symmetric and asymmetric cryptographic algorithms are vulnerable to quantum algorithms. Grover’s search algorithm gives a square root time boost for the searching of the key in symmetric schemes like AES and 3DES. The security of asymmetric algorithms like RSA, Diffie Hellman, and ECC is based on the mathematical hardness of prime factorization and discrete logarithms. The best classical algorithms available take exponential time. Shor’s factoring algorithm can solve the problems in polynomial time. Major breakthroughs in quantum computing will render all the present-day widely used asymmetric cryptosystems insecure. This paper analyzes the vulnerability of the classical cryptosystems in the context of quantum computers, discusses various post-quantum cryptosystem families, discusses the status of the NIST post-quantum cryptography standardization process, provides a performance comparison of post-quantum cryptography (PQC) algorithms on different platforms, and finally provides a couple of future research directions in this field.