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