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 $(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 $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 $\lambda$ be a security parameter and $n=n(\lambda )$ be an integer dimension, let $f(x)=x^{d}+1$ where $d=d(\lambda )$ is a power of $2$, let $q=q(\lambda )\leq 2$ be a prime integer, let $R=\mathbb {Z} [x]/(f(x))$ and $R_{q}=R/qR$, and $\chi =\chi (\lambda )$ be a distribution over $R$. The MLWE instance is a pair of $(a,\langle a,s\rangle +e)$ where $s\gets R_{q}^{n},a\gets R_{q}^{n},e\gets \chi$ uniformly.

PROBLEM. Search - MLWE Problem

Let ${\mathcal {\psi }}$ be a family 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 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 \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 $(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 $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 $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 $(a,\langle a,s\rangle +e)$ from PLWE oracle; in the second distribution, one samples uniformly a pair of $(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 ${-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 $s$ 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 \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 $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 $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 $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 $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 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^{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