格密码基础【论文向】

目录

写在前面

一. 与格相关的线性代数

二. 格的维度与秩

2.1 满秩格

2.2 非满秩格

三. 最短长度

四. 格的行列式

五. 离散高斯分布

5.1 连续高斯分布性质

5.2 格上离散高斯分布

六. 光滑参数

6.1 官方定义

6.2 通俗理解

七. 格基怎么选

---

写在前面

其实之前写过有关格密码的介绍：

格密码的基础概念（1）-CSDN博客

本文章将分析论文中最常使用的那些格密码基础知识。

一. 与格相关的线性代数

接下来，n维单位矩阵通常写为In（identity matrix）。

正交线性变换通常理解为旋转，如下：

其中O代表正交变换，n代表n维矩阵，R代表实数范围

由此可得：

格中最常使用的幺模矩阵（unimodular）通常写为：

其中n代表矩阵维度，Z代表整数范围。

需要注意的是幺模矩阵的行列式为正负1：

二. 格的维度与秩

2.1 满秩格

对于满秩格来讲，m=n，格基B通常写为：

格L=L(B)的维度也为n。格为n维实数范围上的离散子群。进一步可形成子格：

如果子格的维度也是n的话，那么L'就是满秩子格。

2.2 非满秩格

对于非满秩格来讲m>n，格基则是n个m维的列向量，如下：

对于格L=L(B)来讲，格的维度为m，格的秩为n

三. 最短长度

格的最短向量长度通常记为：

一般有两种理解方式：

1. 代表格点之间最短的距离；
2. 最短的非零格向量长度（欧几里得范数）；

所以可以理解为：

进一步会出现连续最小值（successive minimum）：

其中n代表格的维度。

对于连续最小值最通俗的理解就是第一短的格向量长度，第二短的格向量长度，以此类推。但其实这样理解是不对的。比如，第一短的向量和第二短的向量是不能平行的，要实现维度的扩张。换句话说要包含i个线性独立的向量。所以，最正规的理解是：

其中dim代表维度，span代表是数控剪，代表圆心在原点的球

四. 格的行列式

格基矩阵B可以形成Gram矩阵G：

由此格的行列式可以计算为：

需要注意的是，格的行列式通常为正数。通过行列式的计算也可以看出，格基乘以幺模矩阵，格是保持不变的。

Minkowski定理可以描绘格最短向量长度与格行列式det(L)之间的关系：

其中，C为大于0的常数。

五. 离散高斯分布

5.1 连续高斯分布性质

n维连续的高斯分布可以表示为：

其中y为n维向量，s为大于0的标准差。

很明显该连续高斯分布是关于原点对称的，所以在格密码中通常简记为：

在一定的区间内，可以利用积分来求区间概率，如下：

其中集合.

如果仅仅是1维的话，可以简单记作.当然，如果写全的话，则为，只不过上标1通常省略不写。

有一个高斯分布取样的性质在论文中非常多见：从高斯分布中取的数与整数的距离平方趋近于一个固定值，该固定值v为：

从分布的角度来讲就是有中心点，密码学喜欢用概率来表示这种趋势：

其中，且：

证明的过程比较繁琐，就直接列出了：

需要用到如下定理：

1. 高斯函数中的Chernoff-Hoeffding定理
2. Poisson定理
3. 函数积分的基本运算性质
4. 概率模运算的性质
5. 期望运算的基本性质

5.2 格上离散高斯分布

如果将每个格点都带入高斯分布中，便可以得到：

其中s代表高斯分布的标准差。此时便可以得到格点求和的高斯分布值。

那么如果我们衡量单个格点的概率值，不就可以利用单个事件除以总事件得到吗？

由此，我们便可以得到离散高斯分布:

其中分子代表单个格点的概率。分母代表所有格点求和的概率。以上式子中，L代表格，s代表标准差。

六. 光滑参数

6.1 官方定义

首先格基B可以记作：

前面讨论的离散高斯分布取样容易吗？

已有的研究表明当标准差足够大时，离散高斯分布就很好输出样本：

这也揭示出了密码学家很关心标准差所取的大小，由此可得光滑参数的官方定义如下：

其中代表对偶格，。

同样也说明了光滑参数与标准差s紧密相关。

6.2 通俗理解

当标准差大于光滑参数时，也就是：

其中

那么会出现第一种分布：

先从离散高斯分布中取样本X，也就是：

接着将样本X模运算至格基本区内，也就是：

接着第二种分布就是  mod L格基本区上的均匀分布。

光滑参数告诉我们，这两种分布的统计距离为

综合以上，我们可以发现光滑参数主要用来衡量离散高斯分布的标准差应该怎么选。

更进一步，光滑参数与对偶格向量长度的最小值之间存在如下关系：

其中，

七. 格基怎么选

很多时候，我们选择很多格点，比如选出m个格点：

这m个格点也可以形成格，也就是整数组合可以形成其他任意格点：

如果此时m=n的话，那这就是格基，也就是组成该格的格基。

回顾一下，我们知道如果是最简单的整数格，也就是：

那么该格的行列式determinant为1

在格密码的论文中，我们通常习惯用离散高斯抽样算法来进行选取格点，也就是：

注意此时的格就是最简单的整数格。

那么通常需要抽取多少个格点会出现格基呢？

首先离散高斯分布的方差不能太小，也就是：

需要选取的格点数需要超过如下：

那么，即可以作为整数格的格基。