格密码

好看没看格密码了，今天回顾下格密码的一些基础。

格基础知识

定义 已知 是 个线性无关的向量，则基于 的 维格 定义为：

其中 表示为 维实数域，表示为整数域， 称为 格 的一组基，若基向量的个数和格的维度相等，则称为满秩格。

格具有以下性质：

• 加法子群： 且对于任意的 , 有 ;
• 离散性： 对于任意 ， 且存在 ， 满足

若有矩阵 表示格 的基，且基向量为列向量，表示为： , 设 也为列向量，则基于 的格 可以表示为：

定义 已知 是 维格 的一组基，则格 关于 的元域（Fundamental Domain ） 表示为：

命题 已知 是 维格的 的一组基，则有 Hadamard不等式：

定义Hadamard 比为：

对于格 的什么任意一组基， 都有 ， 该比值反映基的两两正交性，若比值接近于1， 则表示基越近于两两正交。 通常，将Hadamard 比接近于1 的基称为好基，接近于0的基称为坏基。

格问题

定义 格 的最短向量距离是指格中最短的非零向量。

大部分格的问题都汲及到格中两个向量或者格中的向量与非格中向量的距离问题，格中的距离一般指欧氏距离。

最短向量问题（SVP） 已知 维格 ， 找到格 中最短非零向量，即找到向量 ， 满足：

近似最短向量问题（） 已知 维格 和 ， 找到 中的非零向量 ， 满足：

其中 是格维度 的函数。

最近向量问题（） 已知 维格 和一个非 中的向量 ， 找到 中向量 ，使得 最小。

近似最近向量问题（） 已知 维格 和一个非 中的向量 ， 找到 中向量 ， 满中：

其中 是格维度 的函数。

最小整数解问题（SIS） 给定矩阵 , 找到向量 ， 满足 且 。

其中 表示 行 列的矩阵，且元素范围为： , 为质数。

SVP 和 CVP 特定条件下都是难于计算的，CVP 问题是NP-hard 问题，常规 SVP 问题在随机约减情况下也是NP-hard问题。 基于不同的难题，就有不同的格密码体制。

最短向量问题

命题 已知 维格 ， 则 .

命题 已知 维格 ， 则 .

最近向量问题

对于 维格 ， 有一组基 ， 满足基向量两两正交，即：

可以很容易的计算该格的SVP 和CVP问题。

例如对于SVP, 格中任意向量的长度可以表示：

由于 可以取任意整数，则最短非零向量一定存在于集合中。

对于CVP， 情况类似。对于非格向量 ， 格向量 的最近距离表示为：

由于， 则当 为最接近 的整数时， 最小。

实际中，只要格的基向量接近于两两正交，也就是好的基，那么将有很大的可能CVP， 反之，如果格的基向量是一个坏基，该方向行不通。

Babai 最近向量算法

已知 维格 ，有一组基 ， 是非格向量，如果 中的向量两两正交或接近两两正交，则可以采用Babai算法求解CVP。

GGH 数字签名

Goldreich, Golfwasser和Halevi 于1997年提出一种基于CVP问题的数字签名算法，简称GGH 数字签名。GGH密码中， 私钥是 维格的 的一个好基，公钥是同格的坏基，密钥生成算法如下：

数字签名，选择一个非格向量 作为签名明文，用好的基求解向量 的CVP 问题，返回的向量即为签名，如下所示：

验证签名的过程就是判断签名明文 是否与签名 足够近，可以验证明文 与签名 的距离是否小于进行判断，其中 ， 用坏的基计算格的行列式，算法如下：

2012年，Lyubashevshy提出一种基于SIS 的数字签名方案，本文不在详细介绍。

参考

https://hal.inria.fr/hal-00864308