(Draft) Lattice-based crypto - introduction
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.