# Lattice based cryptography

(Redirected from IMLWE)

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

${\displaystyle {\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. ${\displaystyle {\textbf {SVP}}}$ – The Shortest Vector Problem

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

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

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

### Finding close vectors

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

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

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

Given a basis ${\displaystyle B}$ of a lattice ${\displaystyle {\mathcal {L}}}$, a target vector ${\displaystyle t\in \mathbb {R} ^{n}}$.
Goal. Find the closest vector ${\displaystyle x}$ in ${\displaystyle {\mathcal {L}}}$ such that ${\displaystyle \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 ${\displaystyle (a,\langle a,s\rangle +e)}$ with ${\displaystyle q}$ is a prime and

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

There are two basic problems in LWE:

PROBLEM. Search - LWE Problem

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

PROBLEM. Decisional - LWE Problem

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

#### 2. RLWE – Ring Learning With Error[RLWE 1]

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

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

PROBLEM. Search - RLWE Problem

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

PROBLEM. Decisional - RLWE Problem

Let ${\displaystyle {\mathcal {\tau }}}$ be a family of distribution over ${\displaystyle 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 ${\displaystyle (a,{\mathcal {U}}_{n})}$ for a random choice of ${\displaystyle (s,\psi )\to U(R_{q}^{V})\times {\mathcal {\tau }}}$, and the same number of uniformly random and independent samples from ${\displaystyle R_{q}\times \mathbb {T} }$.

#### 3. MLWE – Module LWE

The Module Learning With Error problem was first introduced in [MLWE 1] as General Learning with Errors problem. Let ${\displaystyle \lambda }$ be a security parameter and ${\displaystyle n=n(\lambda )}$ be an integer dimension, let ${\displaystyle f(x)=x^{d}+1}$ where ${\displaystyle d=d(\lambda )}$ is a power of ${\displaystyle 2}$, let ${\displaystyle q=q(\lambda )\leq 2}$ be a prime integer, let ${\displaystyle R=\mathbb {Z} [x]/(f(x))}$ and ${\displaystyle R_{q}=R/qR}$, and ${\displaystyle \chi =\chi (\lambda )}$ be a distribution over ${\displaystyle R}$. The MLWE instance is a pair of ${\displaystyle (a,\langle a,s\rangle +e)}$ where ${\displaystyle s\gets R_{q}^{n},a\gets R_{q}^{n},e\gets \chi }$ uniformly.

PROBLEM. Search - MLWE Problem

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

PROBLEM. Decisional - MLWE Problem

Let ${\displaystyle {\mathcal {\psi }}}$ be a family of distribution over ${\displaystyle K_{\mathbb {R} }}$
Goal. Distinguish the following two distributions: in the first distribution, one samples ${\displaystyle (a,\langle a,s\rangle +e)}$ from MLWE oracle; in the second distribution, one samples uniformly a pair of ${\displaystyle (a,{\mathcal {U}}(R_{q}))}$.

#### 4. Poly LWE

The Polynomial Learning With Error problem [PLWE 1] is a polynomial version of LWE. Let ${\displaystyle \lambda }$ be a security parameter and ${\displaystyle n=n(\lambda )}$ be an integer dimension, let ${\displaystyle f(x)=x^{d}+1}$ where ${\displaystyle d=d(\lambda )}$, let ${\displaystyle q=q(\lambda )\leq 2}$ be a prime integer, let ${\displaystyle R=\mathbb {Z} [x]/(f(x))}$ and ${\displaystyle R_{q}=R/qR}$, and ${\displaystyle \chi =\chi (\lambda )}$ be a distribution over the ring ${\displaystyle R}$. The PLWE instance is a pair of ${\displaystyle (a,\langle a,s\rangle +e)}$ where ${\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 ${\displaystyle (a,\langle a,s\rangle +e)}$ from PLWE oracle; in the second distribution, one samples uniformly a pair of ${\displaystyle (a,{\mathcal {U}}(R_{q}))}$.

### SIS – Small Integer Solutions

PROBLEM. SIS – Small Integer Solutions

Given a modulus ${\displaystyle p}$, a set ${\displaystyle B\subset \mathbb {Z} }$ that contains ${\displaystyle {0,1}}$ or ${\displaystyle {-1,0,1}}$, a ${\displaystyle n\times m}$ matrix ${\displaystyle A}$, and a column vector ${\displaystyle s}$ in ${\displaystyle \mathbb {Z} _{q}^{n}}$
Goal. Find a non-zero vector ${\displaystyle x}$ in ${\displaystyle B^{m}}$ such that ${\displaystyle Ax=0{\text{ mod }}q}$.

PROBLEM. Ring SIS - ${\displaystyle {\text{RSIS}}_{n,m,q,\beta }}$

Let ${\displaystyle R=\mathbb {Z} [X]/(X^{n}+1)}$ and ${\displaystyle R_{q}=R/qR}$, where ${\displaystyle n}$ is a power of ${\displaystyle 2}$ and ${\displaystyle q=1mod2n}$. Given a uniformaly random matrix ${\displaystyle A\in R_{q}^{1\times m}}$.
Goal. Find a non-zero vector ${\displaystyle x\in R^{m}}$ such that ${\displaystyle ||x||_{\infty }\leq \beta }$ and ${\displaystyle A\cdot x=0}$.

PROBLEM. MSIS – ${\displaystyle {\text{Module-SIS}}_{q,m,\beta }}$

Let ${\displaystyle R=\mathbb {Z} [X]/(X^{n}+1)}$ and ${\displaystyle R_{q}=R/qR}$. Given a uniformaly random matrix ${\displaystyle A\in R_{q}^{d\times m}}$.
Goal. Find a non-zero vector ${\displaystyle x\in R^{m}}$ such that ${\displaystyle ||x||_{\infty }\leq \beta }$ and ${\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

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
1. On Ideal Lattices and Learning with Errors Over Ring
Vadim Lyubashevsky, Chris Peikert, Oded Regev., 25 Jun 2013.

MLWE
1. Fully Homomorphic Encryption without Bootstrapping
Zvika Brakerski, Craig Gentry, Vinod Vaikuntanathan., 2012.

PLWE