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.
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 existing certificateless signcryption schemes were designed mainly based on the traditional public key cryptography, in which the security relies on the hard problems, such as factor decomposition and discrete logarithm. However, these problems will be easily solved by the quantum computing. So the existing certificateless signcryption schemes are vulnerable to the quantum attack. Multivariate public key cryptography (MPKC), which can resist the quantum attack, is one of the alternative solutions to guarantee the security of communications in the post-quantum age. Motivated by these concerns, we proposed a new construction of the certificateless multi-receiver signcryption scheme (CLMSC) based on MPKC. The new scheme inherits the security of MPKC, which can withstand the quantum attack. Multivariate quadratic polynomial operations, which have lower computation complexity than bilinear pairing operations, are employed in signcrypting a message for a certain number of receivers in our scheme. Security analysis shows that our scheme is a secure MPKC-based scheme. We proved its security under the hardness of the Multivariate Quadratic (MQ) problem and its unforgeability under the Isomorphism of Polynomials (IP) assumption in the random oracle model. The analysis results show that our scheme also has the security properties of non-repudiation, perfect forward secrecy, perfect backward secrecy and public verifiability. Compared with the existing schemes in terms of computation complexity and ciphertext length, our scheme is more efficient, which makes it suitable for terminals with low computation capacity like smart cards.
Basic security requirements such as confidentiality, user authentication and data integrity, are assured by using public-key cryptography (PKC). In particular, public-key signature schemes provide non-repudiation, integrity of transmitted messages and authentication. The presence of a large scale quantum computer would be a real threat to break the most widely used public-key cryptographic algorithms in practice, RSA, DSA, ECDSA signature schemes and Diffie-Hellman key exchange. Thus, all security protocols and applications where these public-key cryptographic algorithms are used are vulnerable to quantum-computer attacks. There are five directions of cryptographic primitives secure against a quantum computer: multivariate quadratic equation-based, hash-based, lattice-based, code-based and supersingular isogeny-based cryptography. These primitives could serve as replacements for current public-key cryptographic algorithms to prepare for post-quantum era. It is important to prioritize the fields to be replaced by post-quantum cryptography (PQC) since it is hard to replace the currently deployed PKC with PQC at the same time. The fields directly connected to human life such as vehicular communications should be the primary targets of PQC applications. This survey is dedicated to providing guidelines for adapting the most suitable post-quantum candidates to the requirements of various devices and suggesting efficient and physically secure implementations that can be built into existing embedded applications as easily as traditional PKC. It focuses on the five types of post-quantum signature schemes and investigates their theoretical backgrounds, structures, state-of-the-art constructions and implementation aspects on various platforms raging from resource constrained IoT devices to powerful servers connected to the devices for secure communications in post-quantum era. It offers appropriate solutions to find tradeoffs between key sizes, signature lengths, performance, and security for practical applications.
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 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 emergence of quantum computing poses a serious threat to traditional communication systems, endangering the security of digital communications and critical infrastructure. Although existing cryptographic algorithms (such as RSA and ECC) rely on the inefficiency of computing large numbers or solving logarithm inequality problems, quantum algorithms (especially Shor's algorithm) can solve these problems efficiently. To mitigate this threat, the field of post-quantum cryptography (PQC) has emerged and focuses on developing cryptographic systems that are resilient to quantum attacks. The main techniques in PQC include lattice-based, hash-based, code-based, and multivariate polynomial cryptography. Lattice-based cryptography is the leading contender, providing high security and supporting good properties such as fully homomorphic encryption, but facing issues related to size and computational efficiency. Hash-based encryption enables strong digital signatures but has limitations. Code-based encryption based on error-correcting codes provides proof of security but requires small size. Multivariate polynomial cryptography has good performance but has drawbacks in some applications. While standardization efforts led by organizations such as NIST continue, PQC is at the forefront of protecting the digital future from the impact of quantum computing, ensuring the integrity and confidentiality of information in the post-quantum era.
The advent of quantum computing poses a profound threat to traditional cryptographic systems, exposing vulnerabilities that compromise the security of digital communication channels reliant on RSA, ECC, and similar classical encryption methods. Quantum algorithms, notably Shor's algorithm, exploit the inherent computational power of quantum computers to efficiently solve mathematical problems underlying these cryptographic schemes. In response, post-quantum cryptography (PQC) emerged as a critical field aimed at developing resilient cryptographic algorithms impervious to quantum attacks. This paper delineates the vulnerabilities of classical cryptographic systems to quantum attacks, elucidates the principles of quantum computing, and introduces various PQC algorithms such as lattice-based cryptography, code-based cryptography, hash-based cryptography, and multivariate polynomial cryptography. Highlighting the importance of PQC in securing digital communication amidst quantum computing advancements, this research underscores its pivotal role in safeguarding data integrity, confidentiality, and authenticity in the face of emerging quantum threats.