---
title: Intro to Lattice-based Cryptography
tags: presentation
slideOptions:
theme: simple
# Black (default) - White - League - Sky - Beige - Simple - Serif - Blood - Night - Moon - Solarized
transition: 'slide'
# none/fade/slide/convex/concave/zoom
#parallaxBackgroundImage: 'https://s3.amazonaws.com/hakim-static/reveal-js/reveal-parallax-1.jpg'
spotlight:
enabled: false
data-auto-animate: true
---

## Intro to Lattice-based Cryptography
### By Daniel Benarroch, July 2020
**Most pictures taken from [Daniele Micciancio's](https://simons.berkeley.edu/talks/basic-mathematics-lattices) & [Chris Peikert's](https://simons.berkeley.edu/talks/lwe-worst-case-average-case-reductions-and-cryptomania) presentations**

---

## Content Lattices

- Motivation
- What is a Lattice?
- Important properties
- Computational problems
- Hard Problems from Lattices
- Regev Encryption

---

## Motivation

- **Mathematics:** used to bridge two fields
- **Cryptanalysis:** many problems can be represented with lattices
- **Post-quantum cryptography:** hard problems against QC

----

### Applications

- Symmetric crypto: PRF / Hashes
- PKC: encryption and signatures (NIST competition)
- Identity/Attribute-based encryption
- **Homomorphic encryption**
- Zero knowledge proofs

---

## What is a Lattice?

<u>**Definition 1**</u>

A lattice $\mathcal{L}$ of $\mathbb{R}^n$ is a discrete subgroup of $\mathbb{R}^n$

1- *additive subgroup*: $\textbf{0} \in \mathcal{L}$, $-\textbf{x}, \textbf{x}+\textbf{y} \in \Lambda$ for every $\textbf{x}, \textbf{y} \in \mathcal{L}$
2- *discrete*: every $\textbf{x} \in \mathcal{L}$ has a neighborhood in $\mathbb{R}^n$ in which $\textbf{x}$ is the only lattice point

(We will talk about full-rank lattices only; i.e.: they span $\mathbb{R}^n$)

----

#### Example 1

Simplest $n$-dimensional lattice is $\mathcal{L} = \mathbb{Z}^n$ and $c\mathcal{L}$ for any $c \in \mathbb{R}$


----

<u>**Definition 2**</u>
A lattice $\mathcal{L}$ is the set of all *integer* linear combinations of *linearly independent* basis vectors $\textbf{B} = \{\textbf{b}_1, ..., \textbf{b}_n\} \subset \mathbb{R}^{n}$

$\mathcal{L} = \textbf{B}\mathbb{Z}^n$ where $\textbf{B}\in \mathbb{R}^{d \times n}$


----

#### Two definitions are equivalent

$2 \implies 1$
1. Existance of shortest vector is equivalent to having a discrete space
2. Parallepiped associated to basis is equivalent to coset group

$2 \Longleftarrow 1$

1. Group defines basis by picking linearly indep vectors. If it does not span $\mathcal{L}$, then find contraction about size of parallepiped

----

### Lattice Basis

We say the (integer) lattice is the span of its basis, written as

$\begin{equation}
\mathcal{L} = \sum^n_{i=1} \textbf{b}_i \cdot \mathbb{Z} = \left\{ \sum^n_{i=1}c_i \textbf{b}_i : c_i \in \mathbb{Z} \right\}
\end{equation}$

where the generating basis matrix

----

### Cosets

As an additive subgroup, we can talk of the quotient group $\mathbb{R}^n / \mathcal{L}$ of cosets

$\begin{equation}
\textbf{c} + \mathcal{L} = \{\textbf{c} + \textbf{v} : \textbf{v} \in \mathcal{L} \}, \textbf{c} \in \mathbb{R}^n
\end{equation}$

> Imagine taking the lattice and moving it around all over the underlying real space. Each position is a coset of the lattice
>
----

### Fundamental Region

The fundamental region of the lattice is the parallepiped

$\begin{equation}
\mathcal{P}(\textbf{B}) := \textbf{B}\cdot \left[-\frac{1}{2}, \frac{1}{2} \right)^n
\end{equation}$

Where different bases define different fundamental regions, all with the same volume, as $\mathrm{det}(\mathcal{L}) = \mathrm{vol}(\mathcal{P}(\textbf{B})) = |\mathbb{Z}^n / \mathcal{L}|$

 

----

> Note that any fundamental region (for different basis and cosets), provides a standard set of representative elements for the coset.

---

## Other important metrics and measurements

1. Minimum distance
2. Successive minima
3. Distance function
4. Covering radius & Smoothing parameter

----

### Minimum distance

$\begin{eqnarray}
\lambda_1 = \lambda_1(\mathcal{L}) &= \min_{\textbf{x}, \textbf{y}\in \Lambda; \textbf{x}\neq \textbf{y}} \|\textbf{x} - \textbf{y} \| \\
&= \min_{\textbf{x}\in \Lambda; \textbf{x}\neq \textbf{0}} \|\textbf{x}\|
\end{eqnarray}$


----

where $\|\textbf{x}\| = \sqrt{x_1^2 + ... + x_n^2}$

> Note that $\lambda_1$ is easy to compute in 2D (Lagrange), but hard in $n$D

----

### Successive minima

The $i$-th successive minimum $\lambda_i(\mathcal{L})$ is the smallest $r$ s.t. $\mathcal{L}$ has $i$ linearly independent vectors of norm at most $r$

Trivial example is in $\mathbb{Z}^n$: $\lambda_1 = \lambda_2 = ... = \lambda_n = 1$


----

### Bounds on $\lambda_i$

- Minkowski #1 $\rightarrow \lambda_1 \leq \sqrt{n}(\det \mathcal{L})^{\frac{1}{n}}$
- Minkowski #2 $\rightarrow (\prod_{i=1}^n \lambda_i)^{\frac{1}{n}} \leq \sqrt{n}(\det \mathcal{L})^{\frac{1}{n}}$

Very analytical proofs.

---

## Some computational problems

From SVP to BDD

----

### Shortest Vector Problem (SVP)

> For an arbitrary basis $\textbf{B}$ of a lattice $\mathcal{L}$, find the shortest non-zero lattice vector: $\textbf{v} \in \mathcal{L}$ s.t. $\|\textbf{v}\| = \lambda_1(\mathcal{L})$. We write $\textbf{v} = \textbf{B}\textbf{x}$ for $\textbf{x} \in \mathbb{Z}^n$


----

### Approximate & Decisional

- Approximate SVP (SVP$_{\gamma}$) $\rightarrow \|\textbf{v}\| \leq \gamma(n)\cdot \lambda_1(\mathcal{L})$
- Decisional approx SVP (GapSVP$_{\gamma}$) $\rightarrow \text{ determine } \lambda_1 \leq 1 \text{ or } \lambda_1 > \gamma(n)$

----

### Approximate SIVP$_{\gamma}$

For an arbitrary basis $\textbf{B}$ of a full-rank, $n$-dimensional lattice, output $\textbf{S} = \{\textbf{s}_i\} \subset\mathcal{L}(\textbf{B})$ of $n$ linearly indep. lattice vectors where $\|\textbf{s}_i\| \leq \gamma(n)\cdot \lambda_n\mathcal{L}$ for all i.


----

### State-of-the-art Attacks

These are well studied problems:

- Lenstra, Lenstra, and Lovasz (LLL) algorithm most well known, **polynomial time for sub-exponential approx factors**
- For polynomial approx factors, only **~exponential time and space**

IMPORTANT: this is also state for quantum algorithms

---

## One more important problem

----

### Distance function

For any point $\textbf{t} \in \mathbb{R}^n$, define the distance to the lattice

$\begin{equation}
\mu(\textbf{t}, \mathcal{L}) = \min_{\textbf{x}\in \mathcal{L}} \|\textbf{t} - \textbf{x}\|
\end{equation}$

----

- One can ask the question of how close is any point to the lattice? Closest Vector Problem (not THAT interesting for crypto)
- Used in coding theory to study level of noise in communication channel


----

### Bounded Distance Decoding (BDD$_{\gamma}$) Problem

> Given $(\mathcal{L}, \textbf{t}, d)$ s.t.
> $\begin{equation} \mu(\textbf{t}, \mathcal{L}) < d = \lambda_1 / (2\gamma(n)) \end{equation}$
> find **unique** $\textbf{v} \in \mathcal{L}$ where s.t. $\|\textbf{t} - \textbf{v}\| < d$

Vector assured to exist; remove the condition to get CVP.

----


---

## Using noise in lattices

----

### Covering radius

Is maximum distance between the lattice and any point in the span of the lattice:

$\begin{equation}
\mu(\mathcal{L}) = \max_{\textbf{t} \in span(\mathcal{L})} \mu(\textbf{t}, \mathcal{L})
\end{equation}$

Spheres of radius $\mu(\mathcal{L})$ cover the whole space


----

### Smoothing lattices

Now imagine adding more and more noise to make uniform distribution

> Radius at most $\|\textbf{r}\| \leq (\log n) \cdot \sqrt{n} \lambda_n$

 

----

### Smoothing parameter

*Best done with Gaussian noise of width $|r_i| \approx \eta_{\epsilon} \leq (\log n) \lambda_n$*

We call $\eta_{\epsilon}$ the smoothing parameter, with several technical results.

> Think about it as the amount of "blur" needed to smooth out the lattice.

---

## Discrete Gaussian Distributions

We recall the basic concepts and definitions, which are used in cryptosystems to make problems hard.

----

### Gaussian function

For any integer $n\geq 1$ and real $s>0$, define Gaussian function of width $s$:
> $\begin{equation} \rho_s(\textbf{x}) := \exp(-\pi\|\textbf{x}\|^2/s^2)\end{equation}$

Where $\rho_s(\textbf{x}) = \prod_{i=0}^n \rho_s(x_i)$; in the continuous setting, it defines a normal distribution


----

### Discrete Gaussian probability

> Defined for a coset $\textbf{c}+ \mathcal{L} \subset \mathbb{R}^n$ and parameter $s>0$, discrete Gaussian by restriction

$\begin{equation}
D_{\textbf{c} + \mathcal{L}, s}(\textbf{x}) \propto \rho_s(\textbf{x}) \text{ if } \textbf{x} \in \textbf{c} + \mathcal{L} \text{; or } 0 \text{ otherwise.} \end{equation}$

----

### Sampling

> For any basis $\textbf{B}$ of a lattice $\mathcal{L}$, for any coset $\textbf{c}+\mathcal{L}$, and any Gaussian $s \geq K$, there is an randomized, poly-time algorithm that outputs a sample of $\mathcal{L}$ that is within statistical distance $\epsilon$ of $D_{\textbf{c}+\mathcal{L}, s}$

----

### Algos

- A variation of "nearest plane" algorithm by Babai'85 is first well known sampling algo, but innefficient.
- Peikert'10 came up with a novel "perturbation" sampling that is quasi-linear
- Brakerski and more...

---

## Cryptographic problems

Foundations and the all-encompassing problem, learning with errors

----

### q-ary Lattices

Cryptography likes to work modulo some integer, $q$. In lattices, the reason is in connection to worst-case vs average-case reductions.

> $\mathcal{L} \subseteq \mathbb{Z}^n$ is integer lattice
> $q\mathbb{Z}^n \subseteq \mathcal{L}$ is periodic modulo small $q$

Functions based on q-are lattices use modulo arithmetic

----

Standard way of building such lattice:

Take matrix
$\mathcal{L}_q(\textbf{A}) = \{ \textbf{x} | \textbf{x} \mod q = \textbf{A}\textbf{u}\textit{ for } \textbf{u} \in \mathbb{Z}^n_q \} \subseteq \mathbb{Z}^n$

- Consider image of $\textbf{A}$, lattice spanned by it
- Can also consider the kernel of this where $\textbf{Au} = 0 \mod q$ and these are reciprocal conditions

----

Confusing note:
> in cryptography one does not need to think about lattices. In some sense, lattices are so nice, that they can apply "post-cryptography" and things will work out.

----

### Short Integer Solution (SIS)

This problem has applications in symmetric crypto.

Informally: for random uniform elements in a group, find an integer linear combination that sums to zero.

----

**Parameters**
- $n$ number of dimensions, main hardness
- $q$ defines the group $\mathbb{Z}^n_q$ (think $q \approx n^2)$
- $\beta$ positive real
- $m$ number of elements

----

#### SIS$_{n,q,\beta, m}$

For $n$ uniformly random vectors $\textbf{a}_i \in \mathbb{Z}^m_q$, rows of matrix $\textbf{A} \in \mathbb{Z}^{n\times m}_q$, find non-zero integer vector $\textbf{z} \in \mathbb{Z}^m$ of short norm $\|\textbf{z}\| \leq \beta$ s.t.

> $\begin{equation} f_{\textbf{A}}(\textbf{z}) := \textbf{Az} = \sum_{i=1}^m \textbf{a}_i \cdot z_i = 0 \in \mathbb{Z}^n_q \end{equation}$

----

**Intuition**

By Gaussian elimition, this would be easy, but large $\textbf{z}$ vector, so require it to be small

- must take $\beta < q$ or trivial solution $\textbf{z}=(q,0,...,0)$ would be legit
- $\beta$ and $m$ must be large enought to ensure existence

----

**Reductions**

- Ajtai'96: SIS reduced GapSVP$_{\gamma}$ and GapSIVP$_{\gamma}$ in the worst-case for $\gamma = \beta\cdot poly(n)$ and $q \geq \beta\cdot poly(n)$
- Best result today by Micciancio and Peikert'13: much lower $q$ and $\gamma$, so smaller keys and stronger guarantees

----

### Ajtai CRF

Think of SIS as a function:

$\begin{equation}
f_{\textbf{A}}(\textbf{x}) = \textbf{Ax} \mod q
\end{equation}$


----

**Concretely**

- Parameters: $m,n,q \in \mathbb{Z}$
- Key: $\textbf{A} \in \mathbb{Z}_q^{n\times m}$
- Input: $\textbf{x} \in \{0,1\}^m$
- Output: $f_{\textbf{A}}(\textbf{x}) = \textbf{Ax} \mod q$

----

**CR**

If collision

> $\textbf{Ax} = \textbf{Ax}' \rightarrow \textbf{Az} = \textbf{A}(\textbf{x}-\textbf{x}') = 0$

where $\textbf{z}$ is short, solution to SIS

----

**Also it is a one-way function**

> If SIVP is hard, then $f$ is a one-way function for $m> n \log q$

----

**Remember the confusing note?**

Note that the $q$-ary lattice $\mathcal{L}'_q(\textbf{A})$ is the kernel of $f_{\textbf{A}}$

- Finding collisions $f_{\textbf{A}}(\textbf{x}) = f_{\textbf{A}}(\textbf{y})$ is equivalent to finding short vectors (SIVP)
- Inverting it is equivalent to CVP under some conditions

We applied lattices given matrices and vectors (integers, modulo $q$)

----

### Regev'05 Learning With Errors

Informally search version: given many noisy inner products $<\textbf{s},\textbf{a}_i> + e_i$ find the secret $\textbf{s}$ common to all

Note that without the error, easy to solve as set of linear equations by Gaussian elimination.

----

**Parameters:**

- dimension $n$
- modulus $q = poly(n)$
- error distribution $\chi$ on $\mathbb{Z}_q$

----

**Search Problem**

Given arbitrary samples below, find $\textbf{s} \in \mathbb{Z}_q^n$


----

**Other form**

$g_{\textbf{A}}(\textbf{s};\textbf{e}) = \textbf{As} + \textbf{e} \mod q$
> Given $\textbf{A}$ and $g_{\textbf{A}}(\textbf{s};\textbf{e})$, recover $\textbf{s}$


----

**Error Distribution**

Think of Gaussian / normal distribution such that stdDev $= \alpha q$


----

**Decision version**

Differentiate between distributions

$\begin{equation}
(\textbf{A}, \textbf{b}) \approx (\textbf{A}, \textbf{u})
\end{equation}$

where $\textbf{u} \in \mathbb{Z}_q^m$ is uniformly random.

----

**LWE as lattice problem**

related to the BDD problem

> $\textbf{v} \in \mathcal{L}$ where s.t. $\|\textbf{t} - \textbf{v}\| < d$
> $\textbf{v} \in \mathcal{L}$ where s.t. $\|\textbf{t} - \textbf{v}\|$ is small
> $\textbf{x} \in \mathbb{Z}_q^n$ where s.t. $\textbf{Ax}+e - \textbf{Ax} \approx 0$

----

**Reductions**

$g_{\textbf{A}}$ is hard to invert on average. Assuming GapSVP, LWE is hard in the worst-case.

GapSVP, SIVP $\leq$ search-LWE $\leq$ decision-LWE $\leq$ Crypto

> search-LWE $\equiv$ decision-LWE

----

**Intuition and Quantumness**

- Best known algoritms (even in quantumness run in exponential time)
- Average-case = worst-case (every problem in the family is hard).
- For any classical alg to solve search-LWE it can translate into quantum alg to solve decision-LWE

> This and the fact that there is no quantum algorithm to solve SVP makes us think it is post-quantum resistant

---

## Cryptographic applications

Regev encryption scheme is used as a basis for many other schemes

----

### Public-key encryption scheme from LWE [Regev05, GPV08]

Say, Alice and Bob want to communicate. Bob will send a message to Alice.

#### Public set up: $parameters = \mathrm{Gen}(\lambda)$

- $n, q, m, \chi$
- Sample $\textbf{A} \in \mathbb{Z}^{n\times m}_q$

----

#### Key generation: $(sk, pk) = \mathrm{Gen}(\textbf{A}, m, n, q)$

- Sample short vector $sk = \textbf{x} \leftarrow \mathbb{Z}^m$
- Compute $pk = \textbf{u} = \textbf{A}\textbf{x}$

> for parameters, if $m > n \log q$ then public key is uniform random vector by LHL

----

#### Encryption: $(\textbf{b}^t, b') = \mathrm{Enc}(bit, \textbf{u})$

- Bob wants to encrypt $bit \in \{0,1\}$
- Sample secret $\textbf{s} \in \mathbb{Z}_q^n$
- Computes "preamble" LWE vector $\begin{equation} \textbf{b}^t = \textbf{s}^t \textbf{A} + \textbf{e}^t \end{equation}$
- Computes payload $\begin{equation} b' = \textbf{s}^t\textbf{u} + e' + bit\cdot \frac{q}{2} \end{equation}$

----

#### Decryption: $bit = \mathrm{Dec}(\textbf{b}^t, \textbf{b}', \textbf{x})$

Alice computes
$\begin{eqnarray}
& \textbf{b}' - \textbf{b}^t \cdot \textbf{x} \\
= & \textbf{s}^t\cdot \textbf{u} - \textbf{s}^t\textbf{Ax} - \textbf{e}^t\textbf{x}+ e' + bit\cdot \frac{q}{2} \\
= & smallError + bit\cdot \frac{q}{2}
\end{eqnarray}$

If result is small, then $bit=0$, otherwise $bit =1$

----

**Putting it together**


----

**Security**

- Eve sees $(\textbf{A},\textbf{u}), (\textbf{b}^t, b')$
- This is LWE samples by multiplying by $\textbf{s}$
- If change the latter with truly uniform samples, $bit$ is hidden informational theoretically
- So based on decision-LWE

----

# Thank You!


---

## Bibliography

[[MicSim20a]](https://simons.berkeley.edu/talks/basic-mathematics-lattices) Daniele Micciancio, *Mathematics of Lattices*, Lattices Bootcamp at Simons Institute

[[MicSim20b]](https://simons.berkeley.edu/talks/sis-worst-case-average-case-reductions-and-minicrypt), Daniele Micciancio, *The Short Integer Solutions Problem and Cryptographic Applications*, Lattices Bootcamp at Simons Institute

[[PeiSim20a]](https://simons.berkeley.edu/talks/lwe-worst-case-average-case-reductions-and-cryptomania) Chris Peikert, *The Learning With Errors Problem and Cryptographic Applications*, Lattices Bootcamp at Simons Institute

[[RegLWE]](https://cims.nyu.edu/~regev/papers/lwesurvey.pdf) Oded Regev, *The Learning with Errors Problem*, survey published online