In the beginning there was the "Bomb", the calculating machine designed by Alan Turing capable of deciphering the enigma messages. At the time, enigma was the safest and most secure cryptographic system used by Nazi forces for military communications, and provided a significant advantage for their operations. Enigma is based on a mathematical problem that has such a complexity that it cannot be addressed by a single individual or by a group of scholars.
For this reason Turing, analyzing the mathematical model that is at the base of the enigma, designed a machine that implemented an algorithm for solving this problem, with the help of electronics that allowed to reduce the execution times of the 'algorithm. Thanks to this machine, the allied cryptographers increased their computational capacity and that allowed them to explore the entire space of searching for solutions until finding the correct answer. This invention was one of the causes that allowed the Allies to win the war with Nazi Germany.
Post quantum algorithms: the 21st century
We have an encryption algorithm based on a mathematical problem that cannot be solved with current tools in an operationally low time frame . The current algorithm that guarantees the security of our communications is RSA (Rivest, Shamir Adleman) , an asymmetric encryption system based on the use of prime numbers. In a nutshell, Alice and bob choose two different prime numbers, these numbers represent their private key. The public key of the system is none other than the product of these two numbers.
The power of this algorithm lies in the fact that the prime number factorization (i.e. finding the private keys) of a number is currently a problem that cannot be solved in polynomial time (i.e. the result arrives, but it is not certain that we will still be alive to admire it. ).
So at the moment there is no "Bomb" capable of breaking this system?
Um, not really. As we can read in several articles , IBM has managed to create the first quantum computer , that is a computer with high computational performance and which would bring current encryption systems to their knees. For this reason, today's mathematical challenges in the cryptographic field converge on the creation of even more complex problems , that is, with a higher computational complexity than that of modern quantum computers.
There are different types of post-quantum algorithms that are being studied to understand whether or not they resist a brute force attack by a quantum computer and they are explained perfectly in this article . We will instead analyze lattice-based cryptography which uses two-dimensional algebraic constructs known as "lattices" , resistant to quantum computation schemes.
A lattice is an infinite grid of points. The computational problem on which lattice-based technology is based is the “Shortest Vector Problem” , which requires identifying the origin of the point in the grid that is closest to a fixed central point in space. In SVP we try to find, given a basis of a geometric lattice, a non-zero vector of minimum norm belonging to the lattice; an approximation of it, very useful in cryptography is SVP γ, that is to find the shortest non-zero vector within an approximation γ. The two problems are both considered computationally very difficult.
What are the benefits of SVP?
As already mentioned, it is a computationally difficult problem, the best post quantum algorithms to solve it have complexity of an exponential order with respect to the size of the lattice. Calculations are performed easily, with a low computational cost. This would make it possible to perform encryption operations even using devices with little computing power and consequently cheaper.
Furthermore, it must be remembered that there are currently no great alternatives to RSA. These alternatives will actually be needed in the case of the discovery of a polynomial time factorization algorithm. A factorization algorithm capable of operating in polynomial time is already known for quantum computers; however, there are currently no known quantum attacks on SVP.
Finally, a very interesting property is that the difficulty of any one instance of the problem is the same as that of the worst case . If we could resolve one instance of this problem, we would be able to resolve all instances, but equally all instances have the same worst case complexity.
Article by Jacopo Iezzi