Lattice-based cryptography
Lattice
- 一個 Lattice (L) ,是由一個彼此線性獨立的向量集合 (B) 產生出來的,這些線性獨立的向量又稱為 Lattice L 的基底(basis)
B={u1,u2,...,uk}⊂Rn
L=n=i∑kZuk
如果 k=n 則可稱這個 Lattice 為 Full-rank lattice
舉個例子:
假設有一組二維向量 {b1,b2}=[10],[01], 及任意整數 x,y
而這個由所有 xb1+yb2 擴展出來的集合就稱為 Lattice(L)∈R2
- Lattice 必須為一個離散循環群 (discrete additive subgroup)
Lattice-based cryptography
困難點在解決 Lattice 中的兩個 NP-hard 問題 :
⎣⎢⎢⎢⎢⎡a11a21⋮am1a12⋱⋯⋯⋱⋯a1n⋮⋮amnq0⋮00q⋯⋯⋱⋯0⋮⋮q⎦⎥⎥⎥⎥⎤⎣⎢⎢⎢⎢⎢⎢⎢⎢⎡s1⋮snk1⋮km⎦⎥⎥⎥⎥⎥⎥⎥⎥⎤=b−e