Background
Quantum computing is widely believed to be a revolutionary new technology. In fact, it is a double-edged sword. If efficient quantum computers can be manufactured in near future, many of the current cryptosystems will be in danger and post-quantum cryptography will be crucial to the security of our communications.
In 1994, P. Shor discovered quantum algorithms which 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 four candidates, CRYSTALS-Kyber, CRYSTALS-Dilithium, Falcon and Sphincs+ for post-quantum cryptography standards. The first three are based on lattice theory and the last on Hash functions. In 2024, NIST announced three 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. On November 12, 2024, NIST published a guideline “Transition to Post-Quantum Cryptography Standards” which includes detailed routes and time tables.
Research Progress
Lattice is a mathematical concept introduced by Gauss in 1831. 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. These problems have been studied by mathematicians including Kepler, Newton, Gauss, Hermite, Minkowski and many others for more than four hundred years. Therefore, post-quantum cryptography is deeply rooted in mathematics.
This paper briefly introduces post-quantum cryptography and its computational complexity foundation, the shortest vector problem (SVP) and the closest vector problem (CVP), then demonstrates in detail their mathematical roots in ball packing, ball covering, and positive definite quadratic forms. In particular, this article emphasizes some problems which will be crucial for the further development of lattice-based cryptography. If we compare post-quantum cryptosystems as fruits, the complexity theory of SVP and CVP will be the fruit trees, and the mathematical theories of lattices and positive definite quadratic forms will be the roots of the trees. This paper shows the whole picture first time, so that both cryptographers and mathematicians can extend their views.
Future Prospects
If a new technology not only can create revolutionary progresses but also disastrous harms, preventing the disasters should be much more important and urgent than gaining the benefits. Quantum computing is such a technology. Therefore, post-quantum cryptography provides unprecedented opportunities for cryptographers and mathematicians to make contributions in modern technology.
No matter how the post-quantum cryptography will develop in the future, mathematics is inevitable since it needs complicated models just like lattices. Of course, only mathematics is not enough. Successful post-quantum cryptography must be a joint work of cryptographers, mathematicians and quantum computing scientists.
The complete study is accessible via DOI: 10.34133/research.0801