Lattice based cryptography

Introduction

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 $\chi \in {\mathcal {\psi }}$.

PROBLEM. Decisional - MLWE Problem

Let ${\mathcal {\psi }}$ be a family of distribution over $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 $(a,{\mathcal {U}}(R_{q}))$.

4. Poly LWE

The Polynomial Learning With Error problem is a polynomial version of LWE. Let $\lambda$ be a security parameter and $n=n(\lambda )$ be an integer dimension, let $f(x)=x^{d}+1$ where $d=d(\lambda )$, 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 the ring $R$. The PLWE instance is a pair of $(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 $p$, a set $B\subset \mathbb {Z}$ that contains ${0,1}$ or ${-1,0,1}$, a $n\times m$ matrix $A$, and a column vector $s$ in $\mathbb {Z} _{q}^{n}$
Goal. Find a non-zero vector $x$ in $B^{m}$ such that $Ax=0{\text{ mod }}q$.

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

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

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

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