Understanding Post-Quantum Cryptography

What is Post-Quantum Cryptography

Post-quantum cryptography refers to modern public key cryptography that can resist known quantum computing attacks. The security of these cryptographic algorithms relies on computational complexity. Post-quantum encryption is a new encryption method that can leverage existing classical computers to achieve resistance against future quantum attacks.

The advantage of post-quantum cryptographic algorithms is that they can cover all scenarios of asymmetric algorithms, and the cost of upgrading and transforming is relatively low; however, the downside is the lack of long-term security proofs, and there remains a possibility of being compromised.

Construction Methods of Post-Quantum Cryptography

1. Lattice-based Post-Quantum Cryptographic Algorithms.A lattice is a mathematical structure defined as an integer linear combination of a set of linearly independent non-zero vectors (called lattice basis). Specifically, given a set of lattice basis, any integer combination of these basis vectors is a vector that belongs to this lattice. A single lattice can have different bases, and solving the shortest vector problem and the closest vector problem in a lattice is currently one of the main NP-hard problems in lattice theory. Additionally, there are other difficult problems in lattices, such as the LWE problem, bounded distance decoding problem, and small integer solution problem. Lattice-based algorithms perform the same functions as modern public key encryption algorithms, enabling encryption and decryption, digital signatures, attribute encryption, homomorphic encryption, key exchange, and various other cryptographic constructions.

In the realm of post-quantum encryption algorithms, by summarizing the currently mainstream lattice-based encryption algorithms, we find that lattice cryptographic schemes based on the LWE hard problem are not only widely applied but also possess higher security.

Regarding post-quantum signature algorithms, the construction of lattice-based signature algorithms differs slightly from existing public key cryptosystems. For existing public key cryptosystems like RSA, ElGamal, and elliptic curves, by swapping the order of public and private keys in the encryption algorithm, they can be converted into signature algorithms. However, lattice-based cryptographic schemes do not have this duality feature. When designing lattice-based post-quantum signature algorithms, zero-knowledge proof protocols are typically used for construction, where the prover demonstrates possession of a private key that matches the corresponding public key without revealing any information about the private key.

2. Code-based Post-Quantum Cryptographic Algorithms.Code theory is a branch of mathematics and computer science that deals with error correction when transmitting information over noisy channels. Code-based cryptographic systems are also considered relatively secure against quantum computers, with the core idea being the introduction of a certain number of error codewords into the encoding, making it difficult to correct these error codewords or calculate the adjoint of the check matrix.

For code-based digital signature schemes, the first code-based digital signature scheme was proposed by scholars in 1990. In 1991, another scholar constructed a public key system that simultaneously had signing, encryption, and error correction capabilities. Subsequently, researchers made a series of improvements based on this foundation, suggesting that code-based public key cryptosystems might serve as a good alternative to number theory-based public key cryptosystems.

3. Hash-based Post-Quantum Cryptographic Algorithms.Hash function-based post-quantum cryptographic algorithms mainly focus on digital signature algorithms. Hash functions exhibit good collision resistance; when a hash function can resist strong collisions, the designed digital signature algorithm can effectively resist quantum computing attacks. Given the unique properties and practicality of hash functions, hash function-based signature algorithms are expected to become one of the most promising digital signature solutions in the quantum era.

4. Multivariate Post-Quantum Cryptographic Algorithms.As one of the earliest members of post-quantum cryptographic algorithms, multivariate post-quantum cryptographic algorithms have more research results compared to the other three mainstream constructions. A multivariate public key cryptosystem maps a set of quadratic polynomials over a finite field as its public key, with the main security assumption being the difficulty of solving nonlinear equations over finite fields, which is an NP-hard problem.

5. Other Post-Quantum Cryptographic Algorithms.In addition to the four mainstream algorithms mentioned above, quantum cryptography and homomorphic cryptographic systems are also within the research scope of cryptographers. In 2006, the concept of “difficult homogeneous spaces” was proposed, laying the foundation for elliptic curve homomorphic cryptographic systems. In the same year, a new general mathematical problem suitable for public key cryptosystems was proposed—computing the homomorphism between given elliptic curves over finite fields. Additionally, ElGamal public key encryption and the Diffie-Hellman key protocol were proposed for homomorphic cryptographic systems. In 2012, candidates for quantum one-way functions were proposed, and researchers studied the distribution of quantum keys under classical authentication key exchange frameworks. In 2014, an undeniable digital signature scheme based on elliptic curve homomorphism was published in academia. In 2017, scholars discussed the cyclic termination fault attacks and first-type fault attacks on super-singular homomorphic cryptosystems. In 2022, different key recovery attack schemes were proposed for super-singular homomorphic key exchange protocols. However, these post-quantum cryptographic algorithms have not yet formed a system like mainstream algorithms.

The Current Development Status of Post-Quantum Cryptographic Algorithms

1. International Development of Post-Quantum Cryptographic Algorithms.The National Institute of Standards and Technology (NIST) in the United States, as the de facto standard-setting body for international cryptographic algorithms, began research on post-quantum cryptographic algorithms in 2012 and initiated an algorithm solicitation in 2016. After three rounds of screening, the first batch of algorithms proposed for standardization was finally announced, taking nearly 10 years. NIST announced that Kyber for public key encryption scenarios and Dilithium, Falcon, and SPHINCS+ for digital signature scenarios will serve as the first batch of standardized post-quantum cryptographic algorithms, with the official standard expected to be released in 2024. Kyber, Dilithium, and Falcon are designed based on lattice mathematical problems, while SPHINCS+ is designed based on hash security problems. Due to the advantages of lattice-based algorithms in security and performance, NIST recommends prioritizing the use of Kyber and Dilithium algorithms, suggesting Falcon for scenarios with limited digital signature lengths, and SPHINCS+ as a backup.

2. The publication date of domestic post-quantum cryptographic algorithm standards has not yet been announced.China’s National Key Laboratory of Cryptography Science and Technology, the China Cryptography Association, and others have conducted discussions on post-quantum cryptographic algorithms and funded algorithm research in the form of projects. The China Cryptography Society held a competition for asymmetric algorithm design in 2018, encouraging submissions of post-quantum cryptographic algorithms that can resist quantum attacks. The results published in 2020 showed that most algorithms are also based on lattice designs.

Glossary

Lattice Basis (RLWE):Given uniformly randomly selected a∈Rq, s∈
\mathcal{R}_q that follows a certain distribution { ext{chi}}_{s}, and e∈Rq that follows a certain distribution { ext{chi}}_{e}, let bi=ais+ei.

LWE:Refers to the Learning With Errors problem, which can be understood as needing to find a set of coefficients such that a linear combination of a set of basis vectors approaches a target vector as closely as possible, using the size of the noise error to define how close we are to the target vector.

RSA:The RSA public key cryptosystem is a cryptosystem that uses different encryption and decryption keys, where deriving the decryption key from the known encryption key is computationally infeasible. RSA is the most widely studied public key algorithm, having undergone nearly 30 years of scrutiny and various attacks, and is widely regarded as one of the best public key schemes available today.

Zero-Knowledge Proof:Is a method by which the prover can convince the verifier that a statement is true without providing any useful information to the verifier.

Hash Function:A function that compresses messages of arbitrary length into a fixed-length message digest.

NP:Non-deterministic Polynomial problem.

Public Key Cryptosystem:Also known as a public key cryptosystem, its principle is the separation of encryption and decryption keys. Users can publicly disclose their designed encryption keys and algorithms while keeping the decryption keys secret. Anyone can use this encryption key and algorithm to send encrypted messages to the user, who can then restore them. The advantage of public key cryptography is that it eliminates the need to transmit keys through secure channels, greatly simplifying key management.

ElGamal Public Key Encryption:The ElGamal encryption algorithm is a public key encryption algorithm based on the discrete logarithm problem. Its basic idea is to encrypt information using a randomly generated key and then decrypt the ciphertext using the public key.

Super-Singular Homomorphic Cryptography:An emerging post-quantum cryptography that resists quantum computers.

Diffie-Hellman Key Protocol:A secure protocol that allows two parties to create a key over an insecure channel without any prior information about each other.