(Very) Basic Intro to Lattices in Cryptography
Tags: bitcoin, cryptography, programming, security
Published: 2020-01-23 14:41:36

---
title: (Very) Basic Intro to Lattices in Cryptography
published: true
date: 2020-01-23 14:38:33 UTC
tags: bitcoin,cryptography,programming,security
canonical_url: https://qvault.io/2020/01/23/very-basic-intro-to-lattices-in-cryptography/?utm_source=rss&utm_medium=rss&utm_campaign=very-basic-intro-to-lattices-in-cryptography
---

By Lane Wagner – [@wagslane](https://twitter.com/wagslane) on Twitter

Lattice-based cryptography has been coming into the spotlight recently. In January 2019, Many of the semifinalists in the [NIST post-quantum-cryptography competition](https://www.nist.gov/news-events/news/2019/01/nist-reveals-26-algorithms-advancing-post-quantum-crypto-semifinals) were based on lattices. Let’s explore the basics of lattices and how they apply to cryptosystems.

## What is a Lattice?

![](https://qvault.io/wp-content/uploads/2020/01/lattice-1024x456.png)<figcaption>A Lattice</figcaption>

According to [Wikipedia](https://en.wikipedia.org/wiki/Lattice-based_cryptography), a lattice is the set of all integer linear combinations of basis vectors:

![{\displaystyle \mathbf {b} _{1},\ldots ,\mathbf {b} _{n}\in \mathbb {R} ^{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/66095403ff779502911d684cccf77daff8981b56)

i.e.

![{\displaystyle L={\Big \{}\sum a_{i}\mathbf {b} _{i}\ :\ a_{i}\in \mathbb {Z} {\Big \}}\;.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bfe3dc9615c168ff919b1c5b229ad392229b8c1d)

More simply put, a lattice is defined by basis vectors, which are only able to be scaled by integers… yay no fractions!

For example, let’s create a lattice of all the integers in a two-dimensional plane:

![](https://qvault.io/wp-content/uploads/2020/01/Capture-1024x740.png)

The definition of our lattice contains only 2 basis vectors,

v1 = (0,1)

v2 = (1,0)

![](https://qvault.io/wp-content/uploads/2020/01/Capture2-1-1024x740.png)

Our lattice is the set of **all** values that can be reached by any combination and scale of our basis vectors. For example, the point (2,0) is in our lattice because it can be reached by 2\*v1

![](https://qvault.io/wp-content/uploads/2020/01/Capture3-1-1024x740.png)

Similarly, we could create an entirely new lattice by changing our basis vectors to

v1 = (0,3)

v2 = (3,0)

![](https://qvault.io/wp-content/uploads/2020/01/Capture5-1-1024x583.png)

As you can see, now the intermediary points (0,1) and (0,1) **no longer exist** in our lattice. There is no way to scale v1 (0,3) and v2 (3,0) to reach those points without using fractional scalars. With lattices, we can only scale by whole integers.

## How Does This Help With Crypto?

Cryptographic algorithms are typically based on mathematical problems that are easy to verify the answer of, but hard to calculate.

For example, RSA is based on prime factorization. If I told you to find prime factors of 27,919,645,564,169,759, that would be hard. However, if I told you that 48,554,491 and 575,016,749 are prime factors, all you have to do is multiply them together in order to verify my answer.

RSA works great with classical computers. There are [no known solutions to find prime factors](https://crypto.stackexchange.com/questions/10590/what-makes-rsa-secure-by-using-prime-numbers) of a number reliably in less than exponential time.

* * *

_In the quantum world, things don't look so peachy. Shor's algorithm on quantum computers can crack RSA in less than exponential time. For this reason, we need quantum-safe algorithms. Many believe that lattice math could be an answer_  
[Click To Tweet](https://twitter.com/intent/tweet?url=https%3A%2F%2Fqvault.io%2F%3Fp%3D587&text=%20In%20the%20quantum%20world%2C%20things%20don%27t%20look%20so%20peachy.%20Shor%27s%20algorithm%20on%20quantum%20computers%20can%20crack%20RSA%20in%20less%20than%20exponential%20time.%20Lattice%20math%20could%20be%20the%20answer&via=wagslane&related=wagslane)

* * *

## Shortest Vector Problem

![](https://qvault.io/wp-content/uploads/2020/01/220px-SVP.svg_.png)

In this introductory article, we will take a brief look at one of the more well-known lattice problems that are of use in cryptosystems, [the shortest vector problem (SVP)](https://en.wikipedia.org/wiki/Lattice_problem#Shortest_vector_problem_(SVP)).

Simply put, the goal of SVP is for the attacker to find the shortest vector from the origin (above in red) when given the basis of a lattice (above in blue). A zero vector doesn’t work as an answer, we consider it trivial.

How is it solved?

Like RSA with classical computers, it is hard to find the shortest vector of a large lattice, especially if it exists in many dimensions. One such slow solution for approximating the shortest vector is [Babai](https://en.wikipedia.org/wiki/L%C3%A1szl%C3%B3_Babai)‘s algorithm, or [Nearest Plane Algorithm](https://cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/cvp.pdf), which you can read about in the links provided.

## Thanks For Reading!

Lane on Twitter: [@wagslane](https://twitter.com/wagslane)

Lane on Dev.to: [wagslane](https://dev.to/wagslane)

Download Qvault: [https://qvault.io](https://qvault.io/)

## Recommended Watching

<iframe title="Chris Peikert: Lattice-Based Cryptography" width="742" height="557" src="https://www.youtube.com/embed/FVFw_qb1ZkY?feature=oembed" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>

The post [(Very) Basic Intro to Lattices in Cryptography](https://qvault.io/2020/01/23/very-basic-intro-to-lattices-in-cryptography/) appeared first on [Qvault](https://qvault.io).