格密码基础
目录
写在前面
本文章主要介绍格密码中所使用的一些基本概念，其中包括：格中基本向量，封闭球内的格点数，半稳定格等等。
一. 格上基本向量
首先，我们知道在数学中有基本向量的概念（或者简称基向量），指的是一组线性无关的向量，并且可以通过线性组合生成整个向量空间。
进而延伸出格中基本向量。
首先在格L上选取一个格向量：
接着对任意的整数a>1，格向量x都不在扩张格上，也就是：
其中格aL可以看成把原格L扩大了a倍。
于是乎，x就被称之为格L的基本向量。
需要注意的是，0向量一般认为不是任何格L的基本向量。因为研究原点在格密码中意义不大。通常，在格密码的论文中，可以将格L中的基本向量全部组合在一起，形成：
二. 封闭球内格点数
可以将格L中长度小于等于r的格向量组合在一起：
等式右边的绝对值符号代表向量数目。
如果将这个概念类推到基本向量，便可以得到：
可以注意到右边有除以2，主要是希望将正负向量x算一个有效的基本格向量。
在格密码中，封闭的Euclidean球一般表示为：
其中2代表Euclidean距离，也就是跟l2范数相关；n代表维度。
铺垫完这些概念，我们来看一个有意思的格点数目问题。
假定维度，球的半径大小满足：
当然，半径的平方要求为整数：
那么可得：
理解：半径为r的球内所包含的整数格点。左边代表下限，右边代表数目上限。
三. 半稳定格
半稳定格的英文为semi-stable lattice
所有格点为n维实数空间的离散子群：
如果发现它所有的子格行列式都大于等于1，也就是：
那么原来的格就可以被称之为半稳定格。
根据格密码的基础概念，相比于原格，子格一定会更加稀疏，也就是行列式会变得更大。
当然，如果恰好原格的行列式为1，也就是det(L)=1，那么这就是一个稳定格（stable lattice）。
可以发现无论是稳定还是半稳定格，都是用行列式的性质来衡量的。接着，来看一个半稳定格内的性质【RS17】。
假定有一常数t，满足：t=10(logn+2)。且要求格L为半稳定格，那么对于任意大于等于1的半径r（）,都有：
理解：半稳定格的球内所包含的格点数目上限。
[RS17] Oded Regev and Noah Stephens-Davidowitz. A reverse Minkowski theorem. In STOC, 2017.3, 9, 17
四. Chernoff-Hoeffding 界
这其实是一个概率论里面的概念，但由于格密码涉及到离散高斯分布，所以会经常用到这个数学中的界限。
假定有M个在[0,1]内独立同分布的随机变量：
independent and identically distributed random variables，也就是论文中常常简写的iid。
有一个大于0的常数s>0，我们可以得到如下概率上界：
简单做一个解释：
ME[Xi]代表任意随机变量期望的M倍
代表对M个变量进行求和
这两者之间的值是相差不大的。
五. 格密码中常用的细节
格密码中的算法的计算复杂度通常习惯表示成与维度n相关的形式。
一般来讲，实数习惯用二进制比特串来表示。
代数（algebraic number）通常用多项式来表示。
随机的正交线性变换R，代表：
这里面蕴含一些线性代数相关的知识。
比如，Gram矩阵里面就包含这种正交变换：
另外，矩阵的QR分解也包含这种正交变换。
之前的博客里面有介绍过QR分解，可参看：
六. 可证明安全的格基
6.1 引入问题
格密码中关于格基，有一个很重要的安全性问题。
举个例子。
我从的旋转格上取样一个格基，形成的困难问题安全吗？
给定一个格，格基我该怎么选？
这里面包含着格密码worst case与average case之间的归约。
当然，刚才谈到的，将n维整数格加上正交变换R，便可以形成旋转格。
作为算法的要求，一般希望对所有符合要求的格基，形成一种分布。这样也更加方便后续进行取样。
6.2 格基选取
首先，我们从格L中选取一定数目的格向量出来：
需要要求这些格点可以形成格L，也就是需要满足：
假定存在一个算法A，可以将这些格点直接转变为格基。
一般在整数格点里面，需要要求该算法是抗旋转的，也就是所谓的rotation invariant。指的是，存在任意正交变换：
利用该算法，都可以得到：
简单看一下这个式子的两边。左边代表算法在输入之前就对每个格点进行旋转。右边代表对算法的输出整体进行旋转。抗旋转则要求，这两则是一样的。
当然，对于确定性算法（deterministic algorithm），要求两者一样。
对于随机性算法（randomized algorithms），则要求两者统计距离接近。
6.3 流程性小结
首先，我们假定存在一个算法A，可以将格点（a generating set）转变为格基。
标准差写做s=s(n)>1.
（1）首先，从整数格内取自离散高斯分布：
（2）输出对应格基B：
（3）判定格基是否满秩：
（4）判定格基行列式是否为1：|det(B)|=1
（5）如果3和4，有一个不满足，则返回1
（6）均匀且随机选取正交变换矩阵：
（7）的旋转格即为
，其对应的格基为：
B'=RB
（8）最终想要的格基分布即可以写做(A,s)-ZDGS.其中A代表转换格基算法，s代表标准差，Z代表整数，DGS代表离散高斯取样。
原文地址：https://blog.csdn.net/forest_LL/article/details/140561012
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！