(Draft) Lattice-based crypto - introduction

October 20, 2021

Page content

During the Corona situation, I decided to learn something new, and it was lattice-based cryptography.

Intro to LWE from knapsack problem

From this slide

1D (modular) knapsack problem

Given $a_{1}, a_{2}, \dots, a_{n}$ and $t$ , $q$ , where all variables are integers. Find ${x_{i}}_{i = 1}^{n} \in {0, 1}^{n}$ s.t. ,

t = \sum_{i = 1}^{n} x_{1} a_{i} mod q .

Vector modular knapsack problem

Given $a a_{1}, a a_{2}, \dots, a a_{n}$ and $t t$ , $q$ , where $a a, t t \in Z^{m \times 1}$ and $q \in Z$ . Find $x x = {x_{i}}_{i = 1}^{n} \in {0, 1}^{m \times 1}$ s.t. ,

t t = \sum_{i = 1}^{n} x_{i} a a_{i} mod q .

We can extend the value of $x_{i}$ from ${0, 1}$ to $x_{i} \in Z$ where $x_{i} ≪ q$ . This extension is $0 - 1$ kanpsack problem -> BKP (Bounded Knapsack Problem) -> UKP (Unbounded Knapsack Problem)

Vector modular knapsack problem in Matrix format

The equation can be expressed in Matrix form. Let $a_{i j}$ be “ $i$ -th element of the vector $\pmb{a}j $” . H e n c e$ t_j = \displaystyle\sum{i=1}^{n} a_{ji}x_i\bmod q $, i f w e d e f i n e a m a t r i x$ \pmb{A} = (\pmb{a}_1, \pmb{a}_2,\cdots,\pmb{a}_n)$, the vector knapsack problem can be expressed as follows:

Given $A A \in Z^{m \times n}$ , $t t \in Z^{m \times 1}$ , and $q \in Z$ . Find $x x \in Z^{n \times 1}$ , s.t.,

A A x x = t t mod q .

How hard to solve the vector knapsack problem

If $n = m$ , the problems can be solved easily by Gaussian elimination ( $O (n^{3})$ ).
If $n \neq m$ , the unbounded knapsack problem (integer knapsack problem) is NP-complete.
Some are solavble in polynomial times. There is an algorithm (LLL lattice basis reduction) to get an approximate answer (or an exact answer sometimes) of this problem in polinomial time ( $O (n^{5} m \log^{3} a)$ where $A$ is the longest length of $a a_{i}$ under the Euclidean norm), under som conditions (refer to Wikipedia).
So, in case of $n \neq m$ , the time complecitiy is NP.

Example of LLL:

https://math.mit.edu/~apost/courses/18.204-2016/18.204_Xinyue_Deng_final_paper.pdf
https://zhenfeizhang.github.io/talks/improve_LLL.pdf
Real value example 1: https://www.youtube.com/watch?v=XEMEiBcwSKc
Real value example 2: https://www.youtube.com/watch?v=n5MfVR77BTw

From knapsack to LWE

We can lead LWE from vector knapsack problem.Here is the step by step instructions. (I omitted all $mod q$ .)

This is a visualized vector knapsack problem:

Split the Matrix $A A$ as follows:

It can be written $A A = [A A^{'} B B]$ .

Multiply $B B^{- 1}$ from left:

Redefine $B B^{- 1} A A$ as $A A$ , and $B B^{- 1} t t$ as $t t$ :

Split the vector $x x$ into $x x =^{t} [s s e e]$ :

Split the multiplication:

And finally, redfine $n - m$ as $n$ :

This is the LWE (Learning With Errors).

Notes

The complexity of finding the inverse $B B^{- 1}$ is $P$ (Gaussian elimination), but the complexity of “finding $s s$ and $e e$ ” is $N P$ , because the complexity of a vector knapsack problem is $N P$ .

LWE problem

The first definition of LWE appears in the famous paper from Regev.

You can find a free version from https://cims.nyu.edu/~regev/papers/qcrypto.pdf.

First, Regev introduced “learning from parity with error problem” as follows:

Let $s s \in Z_{2}^{n}$ , $a a_{i} \in Z_{2}^{n}$ , and $0 \leq ε ≪ 1$ .

Find $s s$ from given pairs $(a a_{i}, b_{i})$ , s.t.,

\begin{aligned} ⟨ s s \cdot a a_{1} ⟩ & \approx_{ε} b_{1} (mod 2) \\ ⟨ s s \cdot a a_{2} ⟩ & \approx_{ε} b_{2} (mod 2) \\ \cdot \\ \cdot \\ \cdot \end{aligned}

where

\approx_{ε}

means “the result is wrong (error) with probability

ε

”.

This problem is one of the simplest 0-1 modular knapsack problem, if there is no error ( $ε = 0$ ).

From this problem we can extend:

$mod 2$ to $mod p$ , where $p$ is a prime integer, and $p \leq p o l y (n)$ .
$ε$ to an error distribution function $Ψ$ .

This extended problem is called ${L W E}_{p, Ψ}$ problem.

Application to public key encryption

At the end of the paper from Regev, they propose how to apply this LWE problem into public key encryption.

Examples

https://www.esat.kuleuven.be/cosic/blog/introduction-to-lattice-based-cryptography-part-2-lwe-encryption/ <- contains some errors.

entities

Plain text: $m \in Z$
Prime number $q$
Dimention $n$
$A A \leftarrow U (Z_{q}^{n \times n})$
$s s \leftarrow Z_{q}^{n \times 1}$
$e e \leftarrow Z_{q}^{n \times 1}$
$s s^{'} \leftarrow Z_{q}^{n \times 1}$
$e e^{'} \leftarrow Z_{q}^{n \times 1}$
$e^{″} \leftarrow Z_{q}$

The $s s$ is a secret key.

How to create public key:

(A A, b b = A A s s + e e mod q)

How to encrypt $m$ :

b b^{'} = A A^{t} s s^{'} + e e^{'} mod q v^{'} = b b^{t} s s^{'} + e^{″} + \frac{q}{2} m mod q

I don’t innerproducts.

How to decrypt $v^{'}$ :

Δ v := v^{'} - {b b^{'}}^{t} s s mod q

It is

\begin{aligned} Δ v & = (b b^{t} s s^{'} + e^{″} + \frac{q}{2} m) - ({s s^{'}}^{t} A A s s + {e e^{'}}^{t} s s) mod q \\ = (s s^{t} A A s s^{'} + e e^{t} s s + e^{″} + \frac{q}{2} m) - ({s s^{'}}^{t} A A s s + {e e^{'}}^{t} s s) mod q \end{aligned}

real value example

Prime number: 17
Dimention: 3
$A A = (\begin{array}{rrr} 3 & 11 & 12 \\ 16 & 2 & 7 \\ 9 & 0 & 1 \end{array})$
$s s^{t} = (\begin{array}{rrr} 1 & 1 & 0 \end{array})$
$e e^{t} = (\begin{array}{rrr} 0 & 1 & 0 \end{array})$

https://www.slideserve.com/felcia/lattice-based-cryptography <- actual values.

LWE definition (Wiki) -> decisional LWE -> RLWE (polynomial) -> NTRU

From Regev’s paper

$\tilde{O}$ : soft-O notation,

f (n) \in \tilde{O} (g (n)) ⟺ \exists k : f (n) \in O (g (n) \log^{k} g (n))