What is a post-quantum cryptography
Post-digital quantum cryptography refers to modern public-key cryptography that can defend against known quantum computing attacks, and the security of such cryptographic algorithms depends on computational complexity. Post-quantum encryption is a new encryption method that can use existing classical computers to achieve sufficient capabilities to withstand future quantum attacks.
The advantage of post-quantum cryptography algorithm is that it can cover all scenarios of asymmetric algorithms and the upgrade cost is low, but the disadvantage is that it lacks long-term security proof, and there is still the possibility of being cracked.
How post-quantum cryptography is constructed
1. Lattice-based post-quantum cryptography algorithms. A lattice is a mathematical construct defined as a linear combination of integer coefficients of a set of linearly independent non-zero vectors (called lattice bases). Specifically, a given set of lattice images is a vector of any integer image that belongs to that lattice. For the same lattice, it can have different lattice bases, and solving the shortest vector problem and the nearest vector problem in lattice is the main non-deterministic polynomial problem in lattice theory. In addition, there are some other difficult problems in the lattice, such as LWE problems, bounded distance decoding problems, and small integer solving problems. The lattice-based algorithm has the same function as the modern public-key encryption algorithm, and can realize a variety of cryptographic constructions such as encryption and decryption, digital signature, attribute encryption, homomorphic encryption, and key exchange.
In terms of post-quantum encryption and decryption algorithms, by summarizing the current mainstream lattice-based encryption and decryption algorithms, we find that the lattice cryptography scheme based on the LWE difficult problem is not only widely used, but also has higher security.
In terms of post-quantum signature algorithms, the construction of lattice-based signature algorithms is slightly different from the existing public-key cryptography. For the existing public-key cryptography such as RSA, ElGamal, and elliptic curves, it can be converted into a signature algorithm by switching the order of the public and private keys of the encryption and decryption algorithm, but the lattice-based cryptographic scheme does not have this dual characteristic, and the zero-knowledge proof protocol is usually used to construct the lattice-based post-quantum signature algorithm, that is, the prover proves that he has a private key that matches the public key of the corresponding identity, but does not disclose any information about the private key.
2. Coding-based post-quantum cryptography algorithms. Coding theory is a branch of mathematics and computer science that deals with error handling when transmitting information in a noisy channel. Coding-based cryptography is also considered to be a relatively secure cryptographic algorithm in quantum computers, and its core lies in introducing a certain number of incorrect codewords into the encoding, and it is difficult to correct the incorrect codewords or calculate the admixture of the check matrix.
In 1990, some scholars proposed the first code-based digital signature scheme. In 1991, another scholar constructed a public key system with signature, encryption and error correction capabilities at the same time. Subsequently, scholars have made a series of improvements on this basis, and pointed out that the code-based public key cryptography may be a good alternative to the number theory-based public key cryptography.
3. Hash-based post-quantum cryptography algorithms. The post-quantum cryptography algorithm based on the Hash function is mainly concentrated in the digital signature algorithm, and the Hash function has good collision resistance, and when the Hash function can resist strong collision, the designed digital signature algorithm can effectively resist the attack of quantum computing. Considering the unique properties of the Hash function and its practicability, the signature algorithm based on the Hash function is expected to become one of the most promising digital signature schemes in the quantum era.
4. Multivariate-based post-quantum cryptography algorithms. As one of the earliest members of post-quantum cryptography algorithms, multivariate-based post-quantum cryptography algorithms have more research results than the other three mainstream construction methods. A multivariate-based public-key cryptography takes a set of quadratic polynomials over a finite field as its public-key mapping, and its main security assumption is to solve the NP-difficult problem of nonlinear equations on a finite field.
5. Other post-quantum cryptography algorithms. In addition to the above four mainstream algorithms, quantum cryptography and homology-based cryptography are also within the scope of research of cryptographers. In 2006, the concept of "difficult homogeneous space" was proposed, which laid the foundation for a cryptosystem based on elliptic curve homology. In the same year, another scholar proposed a new general mathematical problem applicable to public-key cryptography—to calculate the homology between a given elliptic curve for elliptic curves over a finite field. At the same time, ElGamal public-key cryptography and Diffie-Hellman key protocol are proposed for homologous cryptography. In 2012, some scholars proposed a candidate scheme for quantum one-way functions, and some scholars studied the distribution of quantum keys under the classical authentication key exchange framework. In 2014, the academic community announced an undeniable digital signature scheme based on elliptic curve homology. In 2017, scholars discussed the cyclic termination fault attack and the first type of fault attack of the supersingular homologous cryptosystem. In 2022, different key recovery attack schemes were proposed for the ultra-singular homologous key exchange protocol. However, these post-quantum cryptography algorithms have not formed a system like mainstream algorithms.
The development status of post-quantum cryptography algorithms
1. The development of international post-quantum cryptography algorithms. The National Institute of Standards and Technology (NIST), as the de facto standard setter of international cryptographic algorithms, began to start post-quantum cryptography algorithm research in 2012, launched the algorithm collection in 2016, and finally announced the first batch of algorithms to be standardized after three rounds of screening, which lasted for 10 years. NIST announced that Kyber in the public key cryptography scenario and Dilithium, Falcon, and SPHINCS+ in the digital signature scenario will be the first batch of standardized post-quantum cryptography algorithms, and the standards are expected to be officially released in 2024. Kyber, Dilithium, and Falcon are lattice-based mathematical problem designs, and SPHINCS+ algorithms are designed based on hash security problems. Due to the advantages of lattice-based algorithms in terms of security and performance, NIST recommends the Kyber and Dilithium algorithms first, and Falcon is recommended for scenarios where the length of digital signatures is limited, and SPHINCS+ is only used as a backup.
2. The release time of the domestic post-quantum cryptography algorithm standard has not yet been announced. The State Key Laboratory of Cryptography Science and Technology in China and the China Cryptography Association have carried out research on post-quantum cryptography algorithms, and funded algorithm research in the form of projects. In 2018, the Cryptologic Society of China held an asymmetric algorithm design competition to encourage the submission of post-quantum cryptography algorithms that can resist quantum attacks. The results released in 2020 showed that most of the algorithms were also based on lattice design.
Explanation of terms
RLWE: Given a uniformly randomly selected a∈Rq, s\in\mathcal{R}_q obeying a distribution {\chi}_{s}, and e∈Rq obeying a distribution {\chi}_{e}, denoted bi=ais+ei.
LWE: refers to the fault-tolerant learning problem, which can be understood as the need to find a set of coefficients so that the linear combination of a set of basis vectors is infinitely close to the target vector, and the magnitude of the noise error is used to define how close we are to the target vector.
RSA: The RSA public-key cryptography is a cryptosystem that uses different encryption keys and decryption keys, and it is computationally infeasible to derive the decryption key from a known encryption key. RSA is the most widely studied public key algorithm, which has been proposed for nearly 30 years, has experienced the test of various attacks, and is gradually accepted by people, and is generally regarded as one of the best public key schemes at present.
Zero-knowledge proofs: The prover is able to convince the verifier that a certain assertion is correct without providing any useful information to the verifier.
Hash function: A function that compresses a message of any length to a message digest of a fixed length.
NP: A non-deterministic problem of polynomial complexity.
Public-key cryptography: A public-key cryptography that separates the encryption key from the decryption key. Users can make their own encryption keys and algorithms public, and only keep the decryption key secret. Anyone who uses this encryption key and algorithm to send encrypted information to the user can restore it. The advantage of public key cryptography is that it does not need to pass the key through a secure channel, which greatly simplifies key management.
ElGamal public key cryptography: ElGamal cryptography is a public key cryptography algorithm based on the discrete logarithmic problem. The basic idea is to encrypt the information with a key generated by a random number, and then decrypt the ciphertext with a public key.
Ultrasingular homologous cryptography: It is an emerging post-quantum cryptography that resists quantum computers.
Diffie-Hellman Key Agreement: is a secure protocol. It allows two parties to create a key over an insecure channel without any prior information from the other.