Lattice based cryptography
A dimensions lattice is an additive discrete subgroup of . A basis of is a linearly independent set of vectors such that every elements of a lattice is represented as a linear combination of elements in . We say
Contents
Hard Lattice Problems
Finding short vectors
PROBLEM. – The Shortest Vector Problem
Given a basis of a lattice
Goal. Find the shortest vector in
such that .
PROBLEM. – The Approximate Shortest Vector Problem
Given a basis of a lattice
Goal. Find the shortest vector in
such that .
Finding close vectors
PROBLEM. The Closest Vector Problem
Given a basis of a lattice , a target vector .
Goal. Find the closest vector in such that .
PROBLEM. The Approximate Closest Vector Problem
Given a basis of a lattice , a target vector .
Goal. Find the closest vector in such that .
Finding short sets of vectors
Latticebased cryptography
LWE – Learning With Error and its variants
1. Classical LWE
A Learning With Error instance is a pair of with is a prime and
 ,
 ,
 , for some error distribution over .
There are two basic problems in LWE:
PROBLEM. Search  LWE Problem
Goal. Find the secret given access to many independent samples LWE .
PROBLEM. Decisional  LWE Problem
Goal. Distinguish between an unifomrly instance and a sample from LWE oracle .
2. RLWE – Ring Learning With Error^{[RLWE 1]}
Learning with Error over Ring (RLWE) is an invariant of LWE. Let be a number field, be a ring of integers and be a integer. For any fractional ideal in , we let denoted and . A ringLWE instance is a pair of , where
 , uniformly at random.
 .
 , for some error distribution over .
PROBLEM. Search  RLWE Problem
Let be a damily of distribution over .
Goal. Find the secret given access to many independent samples where and .
PROBLEM. Decisional  RLWE Problem
Let be a family of distribution over .
Goal. The averagecase decision version of the ringLWE problem is to distinguish with nonnegligible advantage between arbitrarily many independent samples from for a random choice of , and the same number of uniformly random and independent samples from .
3. MLWE – Module LWE
The Module Learning With Error problem was first introduced in ^{[MLWE 1]} as General Learning with Errors problem. Let be a security parameter and be an integer dimension, let where is a power of , let be a prime integer, let and , and be a distribution over . The MLWE instance is a pair of where uniformly.
PROBLEM. Search  MLWE Problem
Let be a family of distribution over
Goal. Find the secret given access to many independent samples where and .
PROBLEM. Decisional  MLWE Problem
Let be a family of distribution over
Goal. Distinguish the following two distributions: in the first distribution, one samples from MLWE oracle; in the second distribution, one samples uniformly a pair of .
4. Poly LWE
The Polynomial Learning With Error problem ^{[PLWE 1]} is a polynomial version of LWE. Let be a security parameter and be an integer dimension, let where , let be a prime integer, let and , and be a distribution over the ring . The PLWE instance is a pair of where 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 from PLWE oracle; in the second distribution, one samples uniformly a pair of .
SIS – Small Integer Solutions
PROBLEM. SIS – Small Integer Solutions
Given a modulus , a set that contains or , a matrix , and a column vector in
Goal. Find a nonzero vector in such that .
PROBLEM. Ring SIS 
Let and , where is a power of and . Given a uniformaly random matrix .
Goal. Find a nonzero vector such that and .
PROBLEM. MSIS –
Let and . Given a uniformaly random matrix .
Goal. Find a nonzero vector such that and .
Submissions in NIST



Related Articles
A Decade of Lattice Cryptography
Chris Peikert., February 2016.
Comparing proofs of security for latticebased encryption
Daniel J. Bernstein., Jun 2019.
(Survey) The Learning with Errors Problem
Oded Regev..
On the impact of decryption failures on the security of LWE/LWR based schemes
JanPieter D'Anvers and Frederik Vercauteren and Ingrid Verbauwhede.
Cryptology ePrint Archive: Report 2018/1089, Nov 2018.
 ↑ On Ideal Lattices and Learning with Errors Over Ring
Vadim Lyubashevsky, Chris Peikert, Oded Regev., 25 Jun 2013.
 ↑
Fully Homomorphic Encryption without Bootstrapping
Zvika Brakerski, Craig Gentry, Vinod Vaikuntanathan., 2012.
 ↑
Fully Homomorphic Encryption from RingLWEand Security for Key Dependent Messages
Zvika Brakerski and Vinod Vaikuntanathan., 2011.