Lattice-based cryptography

Lattice

1. 一個 Lattice $(L)$ ，是由一個彼此線性獨立的向量集合 $(B)$ 產生出來的，這些線性獨立的向量又稱為 Lattice $L$ 的基底(basis)

$B = \{u_1, u_2, ..., u_k\}\subset \R^{n}$

$L = \sum_{n=i}^{k} \Z u_k$

如果 $k = n$ 則可稱這個 Lattice 為 Full-rank lattice

舉個例子：

假設有一組二維向量 $\{b_1,b_2\} = {\begin{bmatrix}1\\0\end{bmatrix},\begin{bmatrix}0\\1\end{bmatrix},}$ 及任意整數 $x,y$

而這個由所有 $xb_1 + yb_2$ 擴展出來的集合就稱為 Lattice$(L) \in \R^{2}$

2. Lattice 必須為一個離散循環群 (discrete additive subgroup)

Lattice-based cryptography

困難點在解決 Lattice 中的兩個 NP-hard 問題 ：

• Shortest vector problem (CVP):

  • Ring-LWE Signature (Ring learning with errors key exchange)
    
    

• Closet vector problem (CVP):

  • NTRUEncrypt (N-th degree Truncated polynomial Ring Units)

  • BLISS (Bimodal Lattice Signature Scheme)

$\left[\begin{array}{cccccccc} a_{11} & a_{12} & \cdots & a_{1 n} & q & 0 & \cdots & 0 \\ a_{21} & \ddots & & \vdots & 0 & q & & \vdots \\ \vdots & & \ddots & \vdots & \vdots & & \ddots & \vdots \\ a_{m 1} & \cdots & \cdots & a_{m n} & 0 & \cdots & \cdots & q \end{array}\right]\left[\begin{array}{c} s_{1} \\ \vdots \\ s_{n} \\ k_{1} \\ \vdots \\ k_{m} \\ \end{array}\right]=\boldsymbol{b}-\boldsymbol{e}$