lolloj - Fotolia
How lattice-based cryptography will improve encryption
As the prospect of quantum computing-based attacks grows, the need for stronger encryption increases. Expert Michael Cobb discusses lattice-based cryptography as an option.
Cryptographic protocols, such as TLS and HTTPS, sit at the heart of internet security ensuring that communications between two parties are authenticated and private.
Certain encryption algorithms that underpin these protocols -- like RSA, Diffie-Hellman and elliptic curve -- are based on difficult-to-solve mathematical problems and are classified as asymmetric cryptographic primitives.
RSA, for example, is based on the principle that it is easy to calculate the product of two large prime numbers, but finding the factors of a large number, if it has only very large prime factors, is very difficult.
For example, it is easy to check that the product of 31 times 37 is 1,147, but trying to find the factors of 1,147 is a much longer process. The time and resources required to solve these problems are prohibitive, meaning information encrypted using modern encryption algorithms is deemed secure. That is, unless you have a quantum computer, as they can easily solve existing asymmetric cryptographic primitives using Shor's factorization quantum algorithm.
As computing power increases, algorithms need to be retired and replaced. So, for example, the Data Encryption Standard was once the standard algorithm used for encryption, but a modern desktop computer can easily break it. MD5 and SHA-1 were popular hash algorithms, but they are now considered weak, and the National Institute of Standards and Technology (NIST) has already published the successor to SHA-2: SHA-3.
NIST decided the time has come to prepare critical IT systems so they can resist quantum computing-based attacks and has initiated a process to solicit, evaluate and standardize one or more quantum-resistant, public key cryptographic algorithms.
Is lattice-based cryptography the answer?
Many security experts believe that lattice-based cryptography is one way to deliver quantum-resistant encryption. Lattice-based cryptography uses two-dimensional algebraic constructs known as lattices, which are not easily defeated with quantum computing schemes.
A lattice is an infinite grid of dots, and the most important lattice-based computational problem is the Shortest Vector Problem, which requires finding the point in the grid that is closet to a fixed central point in the space, called the origin. This is easy to solve in a two-dimensional grid, but as the number of dimensions is increased, even a quantum computer can't efficiently solve the problem.
The fact that lattice-based cryptography provides fast, quantum-safe, fundamental primitives and enables the construction of primitives that were previously thought impossible, makes it a front runner.
Lattice-based primitives have already been successfully plugged into the TLS and Internet Key Exchange protocols. This means that all the important security protocols can be made quantum-safe by substituting vulnerable problems with problems that are hard for quantum computers to solve using just a couple of extra kilobytes of data per communication session.
Lattice-based cryptography is also the basis for another encryption technology called Fully Homomorphic Encryption or FHE, which could make it possible to perform calculations on files without ever having to decrypt them.
Quantum computing is going to have a profound effect on today's security infrastructure, and enterprises need to consider how they will tackle the security implications sooner rather than later.
