格密码3-格中计算困难性问题1

type

status

date

summary

password

🧐最短距离

除了行列式，格的另一个基本量是格上最短非零向量的长度，即格中最短距离，其定义为

如图，两两格点构成的向量都可以通过平移得到起始点为原点的向量，通过找到距离原点最近的格点即可计算出格中最短距离。格中最短距离也称为第一连续极小，记为1

同理可定义第二至第n连续极小,2,3……n

⛈️

在二维格上，可以用多项式时间算法求解出1，但在多维格上求解1则十分困难。注意，给定一组格基，最短向量不一定是格基之一

🤩距离函数（Distance Function）

给定任意一个点t（这个点不需要在Lattice上），我们可以定义距离函数为这个点到附近的Lattice点的最短距离。

🫣覆盖半径（Covering Radius）

左右移动t的位置，然后就可以找到在这个Lattice中可以得到的最大的。我们一般称这个最大值叫覆盖半径（Covering Radius）

✌️

假设在这个Lattice中，以每个格点为圆心画很多个圆，

如果逐渐把圆的半径扩大的话，那么所有的圆就会逐渐开始覆盖整个空间

🥀格的平滑参数

如果在每个格点上叠加一个圆形范围内取值的随机噪音(生成一个随机值，将这个随机值与圆形范围内的所有格点元的半径相加或替换)，那么当圆的半径达到覆盖半径之后，这个Lattice本身就和背后的连续空间合二为一了

浅浅理解高斯平滑的作用：

缩小r的值，半径对应的向量的每个分向量仅略大

❓为什么要用到平滑参数？

实际上，平滑参数只是定义了一个临界值，当格上的离散高斯分布的标准方差大于此参数时，那么从此分布中选取的点在模格的单元平行多面体中后，几乎将服从均匀随机分布，而当小于此参数时，则不服从均匀随机分布。

🥹Lattice的几何构造

❓为什么要构造

最简单的笛卡尔坐标系整数格,其基向量都是相互垂直的（orthogonal basis），如果我们可以把一个任意的LatticeΛ转换为一个垂直基的格，那么可以更方便简单的在几何空间分析格，比如找到一个格中一个距离t（随意给定的目标值）最近的非零向量v，将其转化为几何空间，只需要通过上下取整，就可以快速找到。