Lattice learning-2

发布于 2021-07-27  81 次阅读





Lattice learning-2

Lattice学习记录

格中的短向量

格中有两个基本问题

  • 最短向量问题(SVP)

    在格​​中寻找一个向量,使它的长度最小。

  • 最接近向量问题(CVP)

    给定一个向量,在格中寻找一个向量,使得最小。

当然这两个问题都可能有多解,从二维的平面坐标我们就可以知道这个事情。不过这两个问题,随着维度​​​的变大,计算也就越困难。之所以我们要解决这两个问题,是因为这两个问题求出的向量,在理论和应用数学的不同领域有许多应用。

在实际中,CVP比SVP更难求解一些,所以我们会把CVP转化成SVP求解。在真实世界的情景中,基于NP-Hard或NP-Complete问题的密码系统倾向于依赖于某种问题的特定子类,以实现效率或允许创建一个trapdoor。 完成后,始终存在所选子类的一些特殊属性,使其更容易地解决而不是常规情况。 我们已经在第6.2节中与Knapsack Cryptosystem中感受过了。

这两个问题还有很多变体,这里就不多介绍了。

Hermite’s theorem and Minkowski’s theorem

我们知道,最短向量的具体长度,取决于格​的维度以及行列式。而这两个定理给出了最短向量的界。

  • Hermite定理:格的维度为,那么它一定有一个向量满足

  • Hermite常数 :对于一个给定的维度​,在格​中一定有一个向量满足

    ​​​是满足这个不等式的最小值,也就是说​​​​。我们目前已知n=1—8,24 这九个值。对于一般的,我们有如下范围

对于Hermite定理,我们有如下推论

其中中的基,这个式子由Hermite定理累乘n次很容易得到。而我们又知道

于是我们就可以在这组不等式两边同时除以​​,然后开n次根号,我们就得到了

  • Hadamard比率

    我们可以知道​​,这个值约接近1,格的这组基就越正交​​。

为了介绍Minkowski定理,我们需要引入几个概念。

  • 封闭球:对于任意和任意,对的封闭球是集合,也就是和​距离不超过R的空间。

  • 的一个子集:

    • 如果中的向量长度是有界的,那么​是有界的。与之等价的,如果有一个半径​,能让被包含在封闭球中,那么是有界的。
    • 若对于,存在,那么是对称的。
    • 若对于中的任意两点​上每一点都在中,那么是凸性集合。
    • 若对于,对于的每个封闭球,都有一个点在里,那么中。如果有这个性质,那么它是封闭的。

Minkowski’s Theorem

​是​中的一个格,​是​中的一个对称凸集,那么​的体积​时,​中就包含一个非零格向量。如果​是封闭的,那么上面的不等式也可以取等号。

Babai’s algorithm

如果说格​有一组基,其中的向量两两正交,那么SVP和CVP都很容易解决。这个算法就是利用了这点。

现有一个向量​,我们把它分解到格的基上,​,我们对每个​取整,记作​,我们就得到新的向量​。

以上就是算法的全部,这个算法在基比较正交的时候可以解决一部分apprCVP问题,但是在基不是很正交的时候,就不适用了。

GHH公钥密码系统

Alice选择的一组基​​作为私钥,这组基的Hadamard ratio不是很小。Alice再选择一个由整数构成的矩阵​,​。计算​,并把​中的行向量​​作为公钥,它们是的一组新的基。

Bob选择明文构成的小向量,再选择一个随机的小干扰向量​,计算

Alice解密时,使用Babai算法计算在原来的基中和最近的向量,然后计算恢复明文。