What is the mathematical foundation of post quantum cryptography?

The mathematical foundation of post-quantum cryptography primarily relies on complex mathematical problems, such as the shortest vector problem (SVP) and closest vector problem (CVP) within lattice theory, which are considered hard to solve even for quantum computers.

Post-quantum cryptography, also called quantum-resistant cryptography, refers to the next stage of operational security, in which only attackers have access to quantum computers (Figure 1).

Lattice basics

A lattice is a multidimensional matrix structure. It’s often visualized as two-dimensional (2D) or three-dimensional (3D) vectors with two or three variables, respectively. In practice, the number of variables in the vectors can be arbitrary, and for cryptography, they are much greater than 3.

Basis vectors are a set of vectors that, when combined using addition or scalar multiplication, can generate every point in the lattice. They define the lattice structure and are often used to create the public key in lattice-based cryptography.

Figure 2 is an example of a 2D lattice formed using two 2D vectors (the black dashed vector and the solid red vectors). That same lattice can be formed using the blue and green dashed vectors. Basis vectors are a fundamental building block of post-quantum cryptography.

In lattice-based cryptography, the public key often relies on a difficult basis or problem like finding the shortest vector, and the private key is based on simpler manipulations of the lattice.

Lattice cryptography is based on the geometry of numbers. This area of mathematics uses the geometry of lattices to solve problems like the SVP and CVP.

Typical lattice operations

Rings, fields, groups, and other concepts from abstract algebra define some operations used in lattice-based cryptography. Error-correcting codes are used in post-quantum cryptography to enhance reliability even in the presence of noise and other interference.

Lattice reduction algorithms are important when solving the SVP and CVP. These algorithms aim to identify a basis with short, nearly orthogonal vectors. The run time can be exponential in the dimension of the lattice, but some algorithms are more efficient because they are polynomial in time.

SVP algorithms

The Lenstra-Lenstra-Lovász (LLL) algorithm is often used to estimate the shortest vector by manipulating the basis of a lattice. The LLL algorithm uses a series of transformations on the lattice basis to find a “reduced” basis where the vectors are shorter and closer to orthogonal.

While the LLL algorithm operates on the entire lattice, the Block Korkine-Zolotarev (BKZ) lattice reduction algorithm operates on a block within the lattice. Both algorithms are iterative, but the BKZ can provide a more efficient methodology for high-dimensional lattices.

The Hermite-Korkine-Zolotarev (HKZ) algorithm also identifies a reduced basis lattice basis. At each step of the iterative process, HKZ selects the shortest vector orthogonal to all the previously chosen basis vectors, resulting in short, nearly orthogonal, vectors and a highly reduced basis.

CVP algorithms

Lattice reduction algorithms are also used to solve the CVP. Babai’s algorithm, also called the “nearest plane algorithm,” has a polynomial running time, not exponential, in the dimension of the lattice. Babai’s algorithm runs recursively until it arrives at a vector guaranteed to have a certain factor of the shortest distance. It’s often combined with LLL reduction to improve solution efficiency.

Kannan’s algorithm explores the lattice to find the shortest non-zero vector. It systematically identifies all lattice points within a specific region, progressively narrowing the search to find the shortest vector. This polynomial-time algorithm is relatively efficient.

Summary

Post-quantum cryptography relies heavily on mathematics related to high-dimensional lattices and their basis and on finding specific vectors within them. Several algorithms have been developed to solve the SVP and CVP efficiently, but this article has only scratched the surface.

References

A Mathematical Perspective on Post-Quantum Cryptography, MDPI mathematics
Development of Modern Cryptography and Research on Quantum Cryptography, NTT
Enhancing Post-Quantum Cryptography: Exploring Mathematical Foundations and Comparative Analysis of Different Cryptographic Algorithm, International Journal for Research in Applied Science & Engineering Technology
Post-Quantum Cryptosystems for Internet-of-Things: A Survey on Lattice-Based Algorithms, MDPI IoT
The Mathematical Foundation of Post-Quantum Cryptography, arXiv
The mathematics behind PQC: the codes, Telsy
Post-quantum cryptography: Lattice-based cryptography, Red Hat
What Is Post-Quantum Cryptography?, National Institute of Standards and Technology
What is Post Quantum Cryptography Encryption?, International Security Journal

EEWorld Online related content

What can be done to prepare for post-quantum cryptography?
Post-quantum crypto standardization — what’s next?
Post-quantum crypto standardization — where we are
Post-quantum crypto standardization — what’s the end game?
Post-quantum crypto standardization — background