Lattice Note 2

Lattice中的各种问题及其联系

最短向量问题SVP

SVP问题的定义：给定一个基为$B$的格$L$，找到一个这个基构成的格点$Bx$，使得这个点到原点的距离最小。

在上图中，$λ_1$为最短向量，基$B=[b_1,b_2]$，我们可以找到一个点$Bx$，即$5b_1-2b_2$这个点，正好对应$λ_1$。需要注意的是，$λ_1$作为最短向量，$Bx$不可能比之还短，最多等于。

当然，如果我们拿到的基不是很好，其实计算严格的SVP（即找出$λ_1$）是一个很难的事情，所以SVP这个问题也有个宽松的版本：$SVP_γ$。

在$SVP_γ$中，问题的设定大致一样，但是唯一不一样的在于，我们找到的点$Bx$，并不一定需要恰好是最短向量$λ_1$，而只要满足小于等于$λ_1$的一个倍数$γ$就行了。

最近向量问题CVP

CVP问题的定义：在连续空间内任意给一点$t$，找距离这个点最近的格点$Bx$。

$$
||Bx||\leλ
$$
此处的$λ$即指覆盖半径。同理可得，CVP也有一个宽松版本$CVP_γ$。

两种CVP问题

给定一个格$L$，与一个随机点$t$还有搜索距离$d$，并且假设$μ(t,L)≤d$，CVP问题是让我们找到一个合理的格点$Bx∈L$并且这个点到$t$的距离小于等于$d$。

CVP问题对于搜索的范围和结果的大小已经有所约束了，但是并没有约束一共有多少结果和范围究竟有多大。所以CVP问题又可以细分为两种主要的版本。

BDD（Bounded Distance Decoding）问题

BDD问题规定了$d<λ1(L)/2$，也就是说$d$小于最短向量的一半。并且这个CVP问题最多只有一个唯一的解，并且这个解一定是距离$t$最近的格点。

ADD（Absolute Distance Decoding）问题

ADD问题则不同，规定了$d≥μ(L)$，也就是说$d$大于整个格的覆盖半径了。这个时候，这个CVP问题至少会有一个解，但是我们找到的解并不一定是距离$t$最近的格点。

最短独立向量问题SIVP

SIVP问题的定义：给定一个格$L(B)$，找到$n$个线性独立的向量$Bx_1,…,Bx_n$并且这些向量的长度都要小于等于最长的最短向量$λ_n$。

这个图就很好的表达了在$n=2$的情况下，我们找到了两个小于等于$λ_2$的点。和SVP与CVP问题一样，我们也可以给出SIVP问题的宽松版定义，即$SIVP_γ$。在宽松版本中，我们只需要找到$γλ_n$范围内的就可以了。

人类就是懒哒😏

基于Lattice的信息传输

首先，我们把需要传输的消息映射到Lattice中的一个点上，即$Bx$，然后我们把$L$,$Bx$发送出去。在接收端我们得到的数据会产生一定程度的偏移，在图上反馈出来就是偏移到了$t$这个点上。我们只需要解决CVP问题，就可以找到原本的格点$Bx$，然后就可以还原出$m$了。

在解决CVP问题的时候，我们还需要知道这个Lattice中最短向量$λ_1$的值来判断CVP问题是不是能够求解出原本的那个点$Bx$。我们需要通过求解SVP问题来得到$λ_1$。

最后，SIVP问题在这里也有所适用。如果我们在传输的过程中为了压缩数据使用了向量量化（Vector Quantization）的方法，在重建向量的时候，需要用到SIVP的解来修复误差。

将ADD问题归约到SIVP问题上

假设我们需要求解ADD(L,t)，我们可以首先用SIVP算法得到这个Lattice的n个独立最短向量V=SIVP(L)。一旦得到了V之后，我们就可以选取这些向量作为基，平分整个多维空间$R_n$。然后我们只需要看t在那个分区中，然后向上或者向下取整一下，找到那个分区对应的格点，就是我们ADD问题的解了。

因为我们是使用了取整的操作来找到格点的，所以这个解的格点到tt的距离，我们也可以找到一个最大的上限，即：
$$
∑_i\frac12||v_i||≤(n/2)λ_n≤nμ
$$

其实我还不是很懂，人麻了