# (Draft) Lattice-based crypto - introduction

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,\cdots, 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_1a_i \bmod q.$$

### Vector modular knapsack problem

Given $\pmb{a}_1, \pmb{a}_2,\cdots, \pmb{a}_n$ and $\pmb{t}$, $q$, where $\pmb{a},\pmb{t}\in\mathbb{Z}^{m\times1}$ and $q \in \mathbb{Z}$. Find $\pmb{x}=\{x_i\}_{i=1}^{n}\in\{0,1\}^{m\times1}$ s.t. , $$\pmb{t}=\sum_{i=1}^{n}x_i\pmb{a}_i \bmod q.$$

We can extend the value of $x_i$ from $\{0, 1\}$ to $x_i\in\mathbb{Z}$ where $x_i\ll 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_{ij}$ be “$i$-th element of the vector $\pmb{a}_j$”. Hence $t_j = \displaystyle\sum_{i=1}^{n} a_{ji}x_i\bmod q$, if we define a matrix $\pmb{A} = (\pmb{a}_1, \pmb{a}_2,\cdots,\pmb{a}_n)$, the vector knapsack problem can be expressed as follows:

Given $\pmb{A}\in\mathbb{Z}^{m\times n}$, $\pmb{t}\in\mathbb{Z}^{m\times1}$, and $q\in\mathbb{Z}$. Find $\pmb{x}\in\mathbb{Z}^{n\times1}$, s.t., $$\pmb{A}\pmb{x}=\pmb{t}\bmod 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^5m\log^3 a)$ where $A$ is the longest length of $\pmb{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:

### From knapsack to LWE

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

This is a visualized vector knapsack problem:

Split the Matrix $\pmb{A}$ as follows:

It can be written $\pmb{A}=\left[\pmb{A}'\ \pmb{B}\right]$.

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

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

Split the vector $\pmb{x}$ into $\pmb{x}=\ ^t[\pmb{s}\ \pmb{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 $\pmb{B}^{-1}$ is $\mathrm{P}$ (Gaussian elimination), so the complexity of “finding $\pmb{s}$ and $\pmb{e}$” is $\mathrm{NP}$, because the complexity of a vector knapsack problem is $\mathrm{NP}$.

### 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 $\pmb{s}\in\mathbb{Z}^{n}_{2}$, $\pmb{a}_i\in\mathbb{Z}^{n}_{2}$, and $0 \leq \varepsilon\ll 1$.

Find $\pmb{s}$ from given pairs $\left(\pmb{a}_i, b_i\right)$, s.t., \begin{align} \left<\pmb{s}\cdot\pmb{a}_1\right> &\approx_{\varepsilon} b_1 (\bmod 2) \\\ \left<\pmb{s}\cdot\pmb{a}_2\right> &\approx_{\varepsilon} b_2 (\bmod 2) \\\ &\ \cdot \\\ &\ \cdot \\\ &\ \cdot \end{align} where $\approx_{\varepsilon}$ means “the result is wrong (error) with probability $\varepsilon$”.

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

From this problem we can extend:

• $\bmod 2$ to $\bmod p$, where $p$ is a prime integer, and $p\leq\mathrm{poly}(n)$.
• $\varepsilon$ to an error distribution function $\Psi$.

This extended problem is called $\mathrm{LWE}_{p,\Psi}$ 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

### entities

• Plain text: $m\in\mathbb{Z}$
• Prime number $q$
• Dimention $n$
• $\pmb{A} \leftarrow \mathcal{U}(\mathbb{Z}_q^{n\times n})$
• $\pmb{s} \leftarrow \mathbb{Z}_q^{n \times 1}$
• $\pmb{e} \leftarrow \mathbb{Z}_q^{n \times 1}$
• $\pmb{s}' \leftarrow \mathbb{Z}_q^{n \times 1}$
• $\pmb{e}' \leftarrow \mathbb{Z}_q^{n \times 1}$
• $e'' \leftarrow \mathbb{Z}_q$

The $\pmb{s}$ is a secret key.

How to create public key: $$\left( \pmb{A}, \pmb{b} = \pmb{A} \pmb{s} + \pmb{e} \bmod q \right)$$

How to encrypt $m$: $$\pmb{b}' = \pmb{A}^t \pmb{s}' + \pmb{e}' \bmod q \\\ v' = \pmb{b}^t\pmb{s}' + e'' + \frac{q}{2} m \bmod q$$ I don’t innerproducts.

How to decrypt $v'$: $$\Delta v := v’ – {\pmb{b}'}^t\pmb{s} \bmod q$$ It is \begin{align*} \Delta v &= \left( \pmb{b}^t\pmb{s}' + e'' + \frac{q}{2}m \right) -\left({\pmb{s}'}^t \pmb{A}\pmb{s} + {\pmb{e}'}^t\pmb{s} \right) \bmod q \\\ &= \left( \pmb{s}^t\pmb{A}\pmb{s}' + \pmb{e}^t\pmb{s} + e'' + \frac{q}{2}m \right) -\left({\pmb{s}'}^t \pmb{A}\pmb{s} + {\pmb{e}'}^t\pmb{s} \right) \bmod q \end{align*}

### real value example

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

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)) \iff \exists k:f(n)\in O(g(n)\log ^{k}g(n))$$