格！

思想

基于王小云等的论文：

[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}_i{b}_i:x_i\in \mathbb{Z},i=1,...,n\}$$

• 格的行列式：$det(L)=vol(P(B))=\sqrt{B^{T}B}$，其中 B 是以格基为列向量构成的矩阵
• 对偶格：$L^{\ast }=\{x\in R^m,\mathrm{\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$，则返回“否”，其他情况随机返回“是”或“否”