Blog Post Sep 23, 2024

Exploring the foundations of lattice-based cryptography

Lattice-based cryptography is a quantum-resistant encryption method that uses complex mathematical lattices, offering security against quantum computing attacks. Unlike traditional encryption methods such as RSA and ECC, which are vulnerable to quantum computers, lattice-based cryptography remains secure due to the computational difficulty of solving lattice problems. It is expected to play a central role in post-quantum cryptography, with applications across government, military, and commercial sectors, ensuring secure communications and data protection in the quantum era.

1. What is lattice-based cryptography?

2. Hard problems in lattice theory

3. Advantages over traditional cryptographic methods

4. How lattice-based encryption works

5. Security & real-world applications of lattice-based cryptography

6. Stay protected in the post-quantum era with Sectigo

Quantum computing is around the corner. This revolution in computing technology promises to shake up everything we currently take for granted about the digital landscape. Unfortunately, unprecedented computing power will leave websites and servers uniquely vulnerable, as tried-and-tested security strategies will no longer be effective.

Current encryption algorithms will not be able to stand up to the power of quantum computing, but thankfully, cryptography is also evolving, and solutions to quantum computing's biggest risks have already emerged. Lattice-based cryptography is one of the new standards that will replace current encryption algorithms, which have now been deemed quantum-vulnerable. We will discuss the power of this type of cryptography in detail below.

What is lattice-based cryptography?

Lattice-based cryptography leverages complex grids or constructions known as lattices for the purpose of encryption and decryption. It involves mathematical problems that remain hard to solve even with the enhanced computational power of quantum machines. Unlike RSA (Rivest Shamir Adleman) and (ECC) Elliptic Curve Cryptography, which can be efficiently broken by quantum computers, lattice-based cryptography is resistant to the vulnerabilities exploited by Shor's algorithm.

These solutions have had a strong reception in recent post-quantum cryptography contests from the National Institute of Standards and Technology (NIST), which regards lattice-based cryptography as the best option for "securing our sensitive data against the possibility of future cyberattacks from quantum computers."

Currently navigating a Post-Quantum Cryptography Standardization program designed to update standards to reflect post-quantum concerns, NIST has selected three algorithms based on structured lattices and one, SPHINCS+, based on hash functions.

Fundamental problems frequently discussed and used for lattice-based solutions include:

Learning With Errors (LWE). Introduced in 2005, LWE introduces errors into vectors, with these errors primarily drawn from probability distributions. These may be referred to as 'noisy' vectors, and LWE aims to uncover the secret vector responsible for producing vectors with errors. This inherent complexity allows LWE to function as a robust framework for lattice-based cryptography.
Shortest Integer Solution (SIS). Similar to LWE, SIS aims to find short non-zero vectors but when lattice coordinates are comprised of integers. This differs from LWE in that vectors remain error-free.

Hard problems in lattice theory

Hard problems form the basis of lattice cryptography; the more difficult these are to solve, the better security they provide. Examples include:

Shortest Vector Problem (SVP). As one of the most extensively studied lattice-based problems, SVP aims to find the lattice's shortest vector that is not also a zero vector (which, technically speaking, would consist of a mere point on the lattice). This is difficult due to the sheer scope of lattices, especially as short vectors become increasingly difficult to pinpoint as lattices grow more complex.
Closest Vector Problem (CVP). Aiming to find the point in a lattice that is closest to a given target point, CVP can be incredibly challenging with high dimensions. This prevents attackers from breaking encryption, as they cannot easily reveal required lattice points near targets.
SVIP (Smallest Value Iteration Procedure). Aligned with the previously described Shortest Vector Problem, SVIP involves an iterative approach designed to help approximate SVP solutions. Such approximations can be helpful when implementing lattice-based schemes. This can contribute to scheme security and quantum resistance while also offering an efficient strategy when searching for short vectors.

Advantages over traditional cryptographic methods

Lattice-based cryptography provides many noteworthy advantages over traditional methods. These benefits vary but generally boil down to one central reality: Shor’s algorithm gives quantum computers the power to easily break RSA and ECC encryption methods, while quantum computers do not have that unfair shortcut for solving lattice problems.

This complexity stems from their big nature, or what Sectigo's Jason Soroko refers to as "10,000-dimension lattices." After all, as he explains, tough math problems are only tough "if you parameterize them correctly and you make the problem large enough." This is exactly what a vast lattice can accomplish.

Other commonly cited benefits include improved key management and crypto agility. Flexible and scalable, lattice-based solutions can be leveraged for many applications but can also be easily adapted to account for evolving threats.

How lattice-based encryption works

Lattice-based encryption relies on a unique grid (known as the lattice), in which sets of points are situated in a criss-cross style. This grid is not finite but rather extends indefinitely. Vectors play a central role in these lattices, originating from a single point but potentially combined in numerous ways to reach every part of the lattice grid.

Vectors that define lattices are often referred to as basis vectors. These can be combined to form the basis of individual points on the grid, and, when multiple basis vectors are added together, it is possible to reach any other point from the lattice.

Public key encryption

Once the lattice's grid and basis vectors have been established, public and private keys become relevant. The public key consists of various vectors that form a 'hard' version of the lattice problem. This is defined as 'hard' not because it presents challenges for encrypting in one direction but rather because it is so difficult to reverse for decryption purposes. A private key (complete with specialized vectors) is necessary for decryption.

Algorithms

Many advanced algorithms play into lattice-based cryptography. These draw heavily on the hard problems highlighted above while providing enhanced security against quantum computing.

Due to their lattice-based foundations, these algorithms are far more future-proof than the once dominant predecessors RSA and ECC. NIST’s winning algorithms that use lattice-based cryptography include:

ML-KEM (Module-Learning with Errors Key Encapsulation Mechanism). As a powerful key encapsulation mechanism, ML-KEM, previously known as CRYSTALS-Kyber, is currently believed to be strong enough to stand up to quantum computers. Key encapsulation mechanisms allow multiple parties to utilize shared secret keys via public channels. These can then be handled alongside symmetric-key cryptographic algorithms to handle essentials such as encryption and authentication.
ML-DSA (Cryptographic Suite for Algebraic Lattices). As part of an important suite of CRYSTALS algorithms, CRYSTALS-Dilithium promotes secure digital signatures and involves a sizable matrix. Leveraging the LWE problem described above, this is most effective for authenticating emails and, moving forward, may play a central role in facilitating secure communications in a post-quantum era.
FN-DSA (Fast Fourier Lattice-based Compact Signatures Over NTRU). Another important digital signature scheme, FALCON is favored for its compact signatures, with exceptional efficiency making this an ideal solution when dealing with limited resources.

Digital signatures

Digital signatures provide a reliable path to verifying message or file authenticity. This strategy relies on a private key for creating the signature, with the recipient then using the public key to confirm the authenticity of the message in question. When lattice-based cryptography is involved in this process, the private key uses basis vectors to define the lattice, while the public key cannot easily facilitate reverse-engineering of the private key.

Security & real-world applications of lattice-based cryptography

Lattice-based encryption algorithms promise to combat both present-day attacks and tomorrow’s most dangerous quantum attacks. Because the quantum era is quickly approaching, NIST and other leaders are in a race to develop powerful lattice-based cryptosystems that can be leveraged in any sector imaginable.

Relevant across industries, lattice-based cryptography is heavily used for government and military purposes, as it facilitates secure communication — especially in settings or situations where unauthorized access to sensitive data could present huge national security risks.

Many commercial enterprises are also beginning to implement lattice-based solutions. In eCommerce, for example, lattice-based solutions promise to improve security for payment processing. Lattice-based cryptography will also prove valuable for Internet of Things (IoT) devices, as this can boost security for data storage and exchange.

Stay protected in the post-quantum era with Sectigo

Quantum computing is right around the corner, and the time to prepare is now. Lattice-based cryptography promises powerful protection and represents the new encryption method standard for addressing the quantum challenges of tomorrow.

At Sectigo, we are on the front lines of post-quantum cryptography. We have developed a dynamic Q.U.A.N.T. strategy to address quantum concerns, featuring these key steps:

Quantum exposure inventory
Uncover risk
Assess and strategize
Navigate implementation
Track and manage

Our certificate lifecycle management platform, Sectigo Certificate Manager, plays an instrumental role in this process, making it easier for organizations to achieve crypto agility. Book a demo today and take an important first step on the path to quantum readiness.