Lattice learning——1

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





Lattice learning-1

Lattice学习记录

Intro

开始学习格密码(寒假学过,但是忘了,而且不会用,坏起来了)。这次学习主要参考,也会参考一些师傅的博客。

我们先来了解一个真实公钥密码系统中的一个简单模型。它的维度很低,不过说明了密码分析中如何出现格。此外,它还提供了对NTRU公钥密码系统的最低维的介绍。

选择了整数作为mod,选择 作为密钥,其中,并且=1,然后计算是公钥。选择明文m和一个随机正整数r,满足,然后计算密文

收到密文后,先计算,这时,再计算。由于上面的限制条件,这里进行mod运算的数都比发送的信息大。

想要从 h 和 q 中获得 f 和 g,也就是获得一组,使得,把这个式子改写为,, 补一个恒等式,我们就可以把它改写成向量的形式:

因此,知道两个向量,她想找到一个线性组合: ,因此,她需要在向量集合中找到一个短的非零向量。而寻找方法,已经由高斯提出,我们会在后面说到。

子集和问题与背包密码系统

  • 子集合问题:

    给定一个正整数集合并选定一个整数,找到的一个子集,使得其中的元素和为。我们可以把这个问题划归成:需要找到一个二进制向量,使得

  • 超级递增序列

    ,其中

有了上面的知识,我们来介绍Merkle -Hellman subset-sum cryptosystem。

  • Merkle -Hellman subset-sum cryptosystem

    选定一个超级递增序列和两个大整数,其中。然后 计算,并把,作为公钥。

    收到密钥后,令密文为,计算,并给 发送S。

    收到密文后,只需要计算,然后求在集合中的一个表示方法,就可以得到密文

以上的密码系统,又被称作子集和密码体制或背包密码体制。由于是一个个整数的列表,每个整数有比特长。明文的长度是,密文的长度是。那么它的信息扩展比是2:1。和RSA以及D-H密码体系相比,它的公钥占用存储空间大,不过它的加密速度很快,历史上,这使得背包密码系统非常有吸引力。但是当LLL格基规约算法被提出后,基于背包问题的加密系统被发现有根本上的漏洞。

下面我们简单介绍一下子集和问题构造的格,也就是它的攻击方法(又要说邪恶的的故事了hhh)想把写成的子集和,她先构造了下面这个矩阵:

取出其中每个行向量,记作,就像之前二维的例子中一样,把这些向量写成线性组合的形式,

既然我们要求的明文​是子集和问题的一个解,而上面的格通过和​​进行点乘运算,可以得到下面这个向量(也就是说中有下面这个向量)

由于是0或1,所以这个向量,而我们知道,于是中的基底长度,这样,我们就可以认为我们找到的这个向量是L里的一个短向量。所以,只需要在中找到一个非零的最短向量,那么就可以认为,找到了我们构造的​,继而恢复明文。

这种在格中找到短向量的算法叫做格基约减算法,其中最著名的就是LLL算法。

向量空间综述

在我们开始之前,我们需要学习 (复习 ) 一些有关向量空间的知识。

  • 向量空间:向量空间是一组向量的集合,这个集合对加法和乘法封闭。
  • 线性组合:令向量集合​​,那么线性组合就是
  • 线性相关与线性无关:有个向量,,若可以找到一组不全为​​的实数使这个等式成立,那我我们就说这组向量线性相关,否则线性无关。
  • 向量夹角
  • 欧几里德范数:也称做向量的长度
  • 施密特正交化方法

格的定义和性质

  • 定义1:令​是一组线性无关的向量,那么格(lattice)就是​这n个向量的线性组合集,即

    这n个向量是L的基底,基底所有的向量数是L的维度。

对于一个格L,可以有很多组不同的基底,而这些基底可以相互转化。这时就需要转化矩阵,使得,由于中的每个元素都是整数,那么我们就要保证中的所有元素都是整数,而其必须满足

  • 定义2:如果​​的一个子集​​对加减法封闭,那么我们就说它是一个加法子群。对​​,如果存在一个正常数​,使得对​中任意一个向量​和​中任意一个向量​,都有,那么是离散加法子群。​​​​

换句话说,就是在中任意取一个向量​,​然后在空间中画一个以​为半径的球,如果在这个球里没有里的其他点,那么就是离散加法子群。

  • 定理:的一个子集是格,当且仅当​是离散加法子群。

  • 定义:基本域:令是一个n维的格,向量是它的一组基,与这组基对应的​​的基本域就是:

    而对于在中的一个向量,我们就可以把它写成,其中是格的一组基底。我们可以发现格​的所有基本域都有相同的体积,而基本域体积不变是格中一个非常重要的性质。并且基本域的体积又被称作的行列式,即