格密码
格！
思想
基于王小云等的论文：
[1]王小云,刘明洁.格密码学研究[J].密码学报,2014,1(01):13-27.DOI:10.13868/j.cnki.jcr.000002.
定义
- 格：格是m维欧氏空间$R^m$的n个线性无关向量组$b_1,b_2,...,b_n$的所有整系数线性组合：
$$ L(B)=\{\sum_{i=1}^{n}x_ib_i:x_i \in \mathbb{Z}, i=1,...,n\} $$
- 格的行列式：$det(L)=vol(P(B))=\sqrt{B^TB}$，其中B是以格基为列向量构成的矩阵
- 对偶格：$L^*=\{x\in R^m,\forall v \in L , <x,v> \in \mathbb{Z} \}$
- 逐次最小长度：第i格逐次最小长度$\lambda_i$，定义为以原点为球心，包含i个线性无关格向量的最小球的半径，即
$$ \lambda_i(L)=inf\{r|dim(span(L \cap B_n(r))) \ge i \} $$
- 堆积半径：对n维格，以格点为球心，r为半径做n维球，使得球两两不相交，最大的r作堆积半径,$r=\lambda_1(L)/2$
- 覆盖半径：对n维格，以格点为球心，r为半径做n维球，能覆盖整个空间的最小r称为覆盖半径。
一些问题
- 最短向量问题（SVP）：给定格L，找一个非零格向量v，满足对任意非零向量$u \in L,||v|| \le||u||$
- $\gamma$-近似最短向量问题（SVP）：给定格L，找一个非零格向量v，满足对任意非零向量$u \in L,||v|| \le \gamma ||u||$
- 逐次最小长度问题（SMP）：给定一个秩为n的格L，找n格线性无关的向量$s_i$，满足$\lambda_i(L)=||s_i||,(i=1,...,n)$
- 最短线性无关向量问题（SIVP）：给定一个秩为n的格L，找n个线性无关的格向量$s_i$满足$||s_i|| \le \lambda_n(L)$
- 唯一最短向量问题（uSVP-$\gamma$）：给定格L，满足$\lambda_2(L) > \gamma \lambda_1(L)$，找到该格的最短向量
- 最近向量问题（CVP）：给定一个格L和目标向量$t \in R^m$，找一个非零格向量v，满足对任意非零向量$u \in L, ||v-t|| \le ||u-t||$
- 有界距离解码问题（BDD-$\gamma$）：给定一个格L，目标向量t满足$dist(t,L)< \gamma \lambda_1(L)$，找一个非零格向量v，满足对任意非零向量$u \in L,||v-t|| \le ||u-t||$
- 判定版本$\gamma$-近似最短向量问题（GapSVP-$\gamma$）：给定格L和一个有理数r，如果$\lambda_1(L)\le r$，则返回“是”，如果$\lambda_1(L)> \gamma r$，则返回“否”，其他情况随机返回“是”或“否”