Lattice based cryptography

From PQC WIKI
(Redirected from MSIS)

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

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

Lattice-based 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 ring-LWE 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 average-case decision version of the ring-LWE problem is to distinguish with non-negligible 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 non-zero vector in such that .


PROBLEM. Ring SIS -

Let and , where is a power of and . Given a uniformaly random matrix .
Goal. Find a non-zero vector such that and .


PROBLEM. MSIS –

Let and . Given a uniformaly random matrix .
Goal. Find a non-zero vector such that and .


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
  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