Lattice based cryptography

A $n$-dimensions lattice is an additive discrete subgroup of $\mathbb {R} ^{n}$. A basis ${\mathcal {B}}$ of ${\mathcal {L}}$ is a linearly independent set of vectors $\{b_{1},b_{2},\ldots ,b_{k}\}$ such that every elements of a lattice ${\mathcal {L}}$ is represented as a linear combination of elements in ${\mathcal {B}}$. We say

${\mathcal {L}}(B)=\{\sum _{i=1}^{k}z_{i}b_{i}\}{\text{ with }}z_{i}\in \mathbb {Z} .$

Hard Lattice Problems

Finding short vectors

PROBLEM. ${\textbf {SVP}}$ – The Shortest Vector Problem

Given a basis $B$ of a lattice ${\mathcal {L}}$
Goal. Find the shortest vector $y$ in ${\mathcal {L}}$ such that $\lVert y\rVert =\lambda _{1}({\mathcal {L}})$.

PROBLEM. ${\textbf {SVP}}_{\gamma }$– The Approximate Shortest Vector Problem

Given a basis $B$ of a lattice ${\mathcal {L}}$
Goal. Find the shortest vector $y$ in ${\mathcal {L}}$ such that $\lVert y\rVert =\gamma \lambda _{1}({\mathcal {L}})$.

Finding close vectors

PROBLEM. ${\text{CVP}}-$The Closest Vector Problem

Given a basis $B$ of a lattice ${\mathcal {L}}$, a target vector $t\in \mathbb {R} ^{n}$.
Goal. Find the closest vector $x$ in ${\mathcal {L}}$ such that $\lVert t-x\rVert \leq {\text{dist}}(t,{\mathcal {L}})$.

PROBLEM. ${\text{CVP}}_{\gamma }-$The Approximate Closest Vector Problem

Given a basis $B$ of a lattice ${\mathcal {L}}$, a target vector $t\in \mathbb {R} ^{n}$.
Goal. Find the closest vector $x$ in ${\mathcal {L}}$ such that $\lVert t-x\rVert \leq \gamma {\text{dist}}(t,{\mathcal {L}})$.

Lattice-based cryptography

LWE – Learning With Error and its variants

1. Classical LWE

A Learning With Error instance is a pair of $(a,\langle a,s\rangle +e)$ with $q$ is a prime and

• $a\leftarrow \mathbb {Z} _{q}^{n}$,
• $s\leftarrow \mathbb {Z} _{q}^{n}$,
• $e\leftarrow \chi$ , for some error distribution $\chi$ over $\mathbb {Z} _{q}^{n}$.

There are two basic problems in LWE:

PROBLEM. Search - LWE Problem

Goal. Find the secret $s$ given access to many independent samples LWE $(a,\langle a,s\rangle +e)$.

PROBLEM. Decisional - LWE Problem

Goal. Distinguish between an unifomrly instance $(a,{\mathcal {U}}(\mathbb {Z} _{q}^{n}))$ and a sample from LWE oracle $(a,\langle a,s\rangle +e)$.

2. RLWE – Ring Learning With Error

Learning with Error over Ring (RLWE) is an invariant of LWE. Let $K$ be a number field, $R$ be a ring of integers ${\mathcal {O}}_{K}$ and $q\leq 2$ be a integer. For any fractional ideal ${\mathcal {J}}$ in $K$, we let ${\mathcal {J}}_{q}$ denoted ${\mathcal {J}}/q{\mathcal {J}}$ and $\mathbb {T} =K_{\mathbb {R} }/R^{V}$. A ring-LWE instance is a pair of $(a,\langle a,s\rangle /q+e{\text{ mod}}R^{V})$, where

• $a\leftarrow R_{q}$, uniformly at random.
• $s\leftarrow R_{q}^{V}$.
• $e\leftarrow \chi$ , for some error distribution $\chi$ over $K_{\mathbb {R} }$.

PROBLEM. Search - RLWE Problem

Let ${\mathcal {\psi }}$ be a damily of distribution over $K_{\mathbb {R} }$.
Goal. Find the secret $s$ given access to many independent samples $(a,\langle a,s\rangle +e)$ where $s\in R_{q}^{V}$ and $\chi \in {\mathcal {\psi }}$.

PROBLEM. Decisional - RLWE Problem

Let ${\mathcal {\tau }}$ be a family of distribution over $K_{\mathbb {R} }$.
Goal. The average-case decision version of the ring-LWE problem is to distinguish with non-negligible advantage between arbitrarily many independent samples from Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (a, \mathcal{U}_n)} for a random choice of $(s,\psi )\to U(R_{q}^{V})\times {\mathcal {\tau }}$, and the same number of uniformly random and independent samples from Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle R_q \times \mathbb{T}} .

3. MLWE – Module LWE

The Module Learning With Error problem was first introduced in as General Learning with Errors problem. Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \lambda} be a security parameter and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n=n(\lambda)} be an integer dimension, let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle f(x) = x^d+1} where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle d=d(\lambda)} is a power of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 2} , let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q = q(\lambda) \le 2} be a prime integer, let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle R=\mathbb{Z}[x]/(f(x))} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle R_q=R/qR} , and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \chi=\chi(\lambda)} be a distribution over Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle R} . The MLWE instance is a pair of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (a,\langle a,s\rangle + e)} where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s \gets R_q^n,a \gets R_q^n, e\gets \chi } uniformly.

PROBLEM. Search - MLWE Problem

Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathcal{\psi} } be a family of distribution over Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle K_{\mathbb{R}}}
Goal. Find the secret Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s } given access to many independent samples Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (a,\langle a,s \rangle +e)} where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s \in R_q^{V}} and $\chi \in {\mathcal {\psi }}$.

PROBLEM. Decisional - MLWE Problem

Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathcal{\psi} } be a family of distribution over Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle K_{\mathbb{R}}}
Goal. Distinguish the following two distributions: in the first distribution, one samples Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (a,\langle a,s\rangle + e)} from MLWE oracle; in the second distribution, one samples uniformly a pair of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (a, \mathcal{U}(R_q))} .

4. Poly LWE

The Polynomial Learning With Error problem is a polynomial version of LWE. Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \lambda} be a security parameter and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n=n(\lambda)} be an integer dimension, let $f(x)=x^{d}+1$ where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle d=d(\lambda)} , let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q = q(\lambda) \le 2} be a prime integer, let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle R=\mathbb{Z}[x]/(f(x))} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle R_q=R/qR} , and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \chi=\chi(\lambda)} be a distribution over the ring Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle R} . The PLWE instance is a pair of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (a,\langle a,s\rangle + e)} where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a \gets R_q, s,e\gets \chi } uniformly.

PROBLEM. Decisional - PLWE Problem

Goal. The decision version of the PLWE problem is to distinguish the following two distributions: in the first distribution, one samples Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (a,\langle a,s\rangle + e)} from PLWE oracle; in the second distribution, one samples uniformly a pair of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (a, \mathcal{U}(R_q))} .

SIS – Small Integer Solutions

PROBLEM. SIS – Small Integer Solutions

Given a modulus Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p} , a set Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle B \subset \mathbb{Z}} that contains Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {0,1}} or Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle {-1,0,1}} , a Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n \times m} matrix Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle A} , and a column vector Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle s} in $\mathbb {Z} _{q}^{n}$
Goal. Find a non-zero vector Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x} in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle B^m} such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle A x = 0 \text{ mod } q} .

PROBLEM. Ring SIS - Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \text{RSIS}_{n,m,q,\beta}}

Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle R = \mathbb{Z}[X]/(X^n+1)} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle R_q=R/qR} , where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle n} is a power of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 2} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle q = 1 mod 2n} . Given a uniformaly random matrix Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle A \in R_q^{1 \times m}} .
Goal. Find a non-zero vector Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x\in R^m} such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle ||x||_{\infty} \le \beta} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle A\cdot x = 0 } .

PROBLEM. MSIS – Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \text{Module-SIS}_{q,m,\beta}}

Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle R = \mathbb{Z}[X]/(X^n+1)} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle R_q=R/qR} . Given a uniformaly random matrix $A\in R_{q}^{d\times m}$.
Goal. Find a non-zero vector Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x\in R^m} such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle ||x||_{\infty} \le \beta} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle [I|A] \cdot x = 0 } .

Submissions in NIST

KEM [10 schemes] Proposal Structures CRYSTALS-KYBER MLWE FrodoKEM LWE LAC Poly-LWE NewHope RLWE NTRU NTRU NTRU Prime NTRU Prime Round5 RLWR SABER MLWR Three Bears IMLWE

PKE (1 scheme) Proposal Structures Round5 MLWE

Signatures (3 schemes) Proposal Structures CRYSTALS-DILITHIUM MLWE FALCON NTRU qTESLA RLWE

Related Articles

GENERAL

A Decade of Lattice Cryptography
Chris Peikert., February 2016.

Comparing proofs of security for lattice-based encryption
Daniel J. Bernstein., Jun 2019.

LWE

(Survey) The Learning with Errors Problem
Oded Regev..

On the impact of decryption failures on the security of LWE/LWR based schemes
Jan-Pieter D'Anvers and Frederik Vercauteren and Ingrid Verbauwhede.
Cryptology ePrint Archive: Report 2018/1089, Nov 2018.

RLWE

MLWE

PLWE