A brief introduction to lattice theory

Can any patterns be observed in these images? Are there common elements? What if I said they are related to post-quantum cryptography? But what is post-quantum cryptography?

The threat of quantum computing is already here. Quantum computers represent a revolutionary evolution in the field of computing. Unlike classical computers, which use conventional bits to store and process information in the form of 0s and 1s, quantum computers leverage the principles of quantum mechanics to represent and manipulate data in the form of qubits. These qubits can exist in multiple states simultaneously thanks to the phenomenon of superposition, allowing quantum computers to process and analyze vast amounts of information exponentially faster than traditional systems. However, it also poses significant challenges in terms of cybersecurity, as current encryption algorithms could become vulnerable to the ability of quantum computers to perform faster factorization and search operations. Post-quantum cryptography is a completely novel branch of cybersecurity that addresses the growing concern about the vulnerability of current encryption systems to future advances in quantum computing. To tackle this concern, the National Institute of Standards and Technology (NIST) in the United States has led a process for evaluating and standardizing post-quantum cryptography algorithms. This process involves identifying, evaluating, and selecting new algorithms that are resistant to quantum attacks, with the goal of establishing robust standards for information security in the future. In 2022, two schemes for both encryption and signature were standardized: CRYSTALS-Kyber and CRYSTALS-Dilithium, both based on lattice theory.

The formal definition of a lattice should not be taken too seriously, as this contribution is merely symbolic. However, what should be clear is that a lattice is a set (most often infinite) that is composed of combinations of vector sums. But how is a lattice constructed?

On the other hand, if we consider the vectors , for example: After all, it is clear that to construct a lattice, it is enough to know how to add and multiply the vectors by integer numbers.

Did you know that the only lattice that does not have infinitely many elements is the zero lattice? In other words, the only lattice that does not have infinitely many elements and that also has just one element is the one whose vector is the zero vector. Does that make sense? Suppose we have two vectors; if these are equal to zero and we make the integer combinations, we are left with only the zero vector because On the other hand, if we have a vector that is not zero, such as, , since there are infinitely many integers, if they are combined, they yield infinitely many points in the lattice.

In the examples presented, all the dot products of the vectors have been zero, since y . are orthogonal. In this case, the dot product is equal to zero, as . When this happens, it is said that the vectors are orthogonal. Now, we can propose the idea of constructing non-orthogonal lattices, or in other words, that their vectors are not perpendicular.

Although it may seem that functions are always drawn and sketched in a plane with a reference axis OX and OY, in reality, it is just a Cartesian reference axis, and there are more reference axes. A reference axis is the affine reference system. This consists of considering the vectors AB and BC from three non-collinear points, A, B, and C. In this case, when we have the 'numbers' on the axis for counting, we will not count one by one but rather make jumps of length and .

Mathematics is composed of different areas of study:

• Algebra (matrices, equations, determinants,...)
• Analysis (functions, integrals, derivatives,...)
• Statistics (populations, frequencies, probabilities,...)
• Geometry and topology

The difference between geometry and topology is that the former studies the quantitative properties of geometric objects (such as calculating areas, perimeters, etc.), while topology studies qualitative properties. For example, to a person studying topology, a donut and a mug are practically identical!

Within topology, time and effort are dedicated to measuring and studying distances (among other things). So far, we have only encountered Euclidean distance, which is the usual one we use in our daily lives, like when using a ruler. However, there is a distance called taxi distance (or Manhattan distance). In taxi distance, we cannot move from one point to another in a straight line (unless they are right next to each other); instead, we have to move as if we were navigating a grid, like in a city. Obviously, this term comes from how taxis navigate through the city, going around buildings along long streets. Don't these cities resemble lattice structures? Let's look at an image of Barcelona:

To conclude this activity, it should be emphasized that a new concept has been introduced: that of a lattice, which is the foundation of the innovative post-quantum cryptography. Connections have been established between lattices and various concepts, such as orthogonality, affine references, and taxi distance. Additionally, this interesting mathematical object has been presented to the students, demonstrating that it exists in nature, encouraging them to gain a broader perspective on mathematics and to recognize that it is more prevalent than they might think.