Applications

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

Example 1

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

Definition 2
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.

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.

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

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.

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.

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…

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

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!