Lattice-based cryptography

Lattice

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

B={u1,u2,...,uk}RnB = \{u_1, u_2, ..., u_k\}\subset \R^{n}

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

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


舉個例子:

假設有一組二維向量 {b1,b2}=[10],[01],\{b_1,b_2\} = {\begin{bmatrix}1\\0\end{bmatrix},\begin{bmatrix}0\\1\end{bmatrix},} 及任意整數 x,yx,y

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


  1. 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)

[a11a12a1nq00a210qam1amn0q][s1snk1km]=be\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}