格密码基础：详解LWE问题（2）

目录

一. LWE问题的标准式

二. LWE单向函数与SIS单向函数

2.1 SIS问题的标准型

2.2 SIS与LWE标准型之间的关系

三. LWE问题有多难？

3.1 结论

3.2 归约过程

四. LWE归约性质

五. LWE问题的两个版本

---

一. LWE问题的标准式

系列文章：

格密码基础：详解LWE问题-CSDN博客

LWE 标准式，英语写做 LWE normal form，有的时候也称之为Hermite标准式。

SIS问题和LWE问题都有标准式，在此类问题中秘密s也是选自误差分布（error distribution）X，当然抽取的结果需要模q，这种选取私钥的方式对密码学的应用很好好处。

忽略样本个数m的区别，Applebaum证明了不论私钥s选自于什么分布（比如均匀分布，高斯分布），其LWE的困难性是类似的，包含search版本和decision版本。

将LWE问题的instance中矩阵A和向量b写做如下：

上式子中矩阵A1是方阵，所以可以求逆，如下：

对应的向量b1也是n维的，如下：

于是乎将原LWE问题的实例（instance），也就是矩阵A和向量b转换为如下：

A2和A1是均匀且随机选取的，且A2与A1互相独立，所以很明显矩阵也是均匀且随机的。

接下来我们考虑原LWE分布，秘密s为n维列向量如下：

向量b1和b2可以写做：

当然毫无疑问误差e是选自噪声分布X的，

由此带入可得：

将此等式看成新的LWE分布，也就是秘密向量为e1，如果e1可以求出来的话，那么可得：

也就是此新的LWE分布的困难性和之前LWE分布求s的困难性是一样的。

如果把目光聚焦在LWE decision问题上。

如果原LWE分布中,b真的是从均匀分布中选择，与矩阵A无关，那么可以马上推出向量也是均匀分布的，而且跟矩阵无关。此时，则证明了两者的decision问题的困难性也是一样的。

二. LWE单向函数与SIS单向函数

通过标准式的格式，我们发现LWE与SIS的标准型很类似，通常来讲，我们会把SIS函数看成满射(surjective)的单向函数，LWE看成单射（injective）的单向函数。

2.1 SIS问题的标准型

在不影响密码学的安全性下，SIS问题的标准型可以把矩阵A缩减n列。首先矩阵A可以分成A1和A2，如下：

其中矩阵A1为n阶方阵，所以可以求逆，由此可得：

可以将上式子中的In看成隐含的单位阵。因为矩阵A2均匀分布，且A2与A1之间互相独立，所以明显矩阵是均匀且随机的。

矩阵A对应的SIS问题的解，与矩阵对应的SIS问题的解是一样的。

所以SIS问题的标准型和原问题的困难性是一样的。但是矩阵的列数变少了，由此获得了优化。

2.2 SIS与LWE标准型之间的关系

SIS满射函数的输入为短向量x，如下：

输出为：

LWE单射函数的输入为短向量e，如下：

输出为：

两者的相差一个正负号。

由于满射函数与单射函数之间的不同，所以两者的密码学应用也会产生一些差异。

三. LWE问题有多难？

3.1 结论

参数m=poy(n)，对应的模数q满足：

离散高斯分布X的参数满足：

利用量子归约，解决decision-LWE问题的困难性相等于在任意n维格上解决近似GapSVP和SIVP问题，其中近似因子为：

完整的形式化表达如下：

熟悉的小伙伴会发现这跟最坏情况下的SIS问题是类似的。m和q的值其实对困难性无影响，其中q需要满足：

近似因子与LWE问题中的相关。

3.2 归约过程

借助LWE的oracle，利用多项式时间的量子归约算法可解决最坏情况下的近似GapSVP和SIVP问题。这句话可能有点隐晦，简单解释下：

如果存在一个算法可以解决LWE问题，那么我们马上可以将其转为解决格问题的量子算法。

需要注意的是，目前还没有已知的量子算法可以解决近似GapSVP和SIVP问题。当然，一般来讲，用了量子算法时，会更快一点。

实际上，在2009年，Peikert也给出一种经典归约的算法。

四. LWE归约性质

通过量子归约（quantum reduction），Search-LWE问题的困难性与最坏情况的格问题类似。其归约过程有两个重点：

重点1：

假定存在一个oracle可以解决Search-LWE问题，给出一个格上离散高斯分布其参数为r，那么就可以利用经典归约解决对偶格上的BDD问题（bounded-distance decoding），其中距离d为：

此过程只需要将BDD的instance和高斯样本结合，来产生LWE样本。LWE oracle会输出对应的秘密，由此我们便可以得到BDD问题的答案。

重点2：

如果在对偶格上，解码距离为d，拥有对应的oracle，那么我们就可以利用量子算法产生格L上的离散高斯样本，其中参数为：

此过程既可以借助量子计算来产生BDD instance的答案，接着借助量子傅里叶变换，既可以产生离散高斯样本。

第一个重点告诉我们：

由于：

由此可得：

迭代操作如上两步，便可以产生离散高斯样本，最终解决近似GapSVP和SIVP问题。

五. LWE问题的两个版本

忽略样本数m的变化，借助基本的经典归约，在网络安全领域，decision LWE问题的困难性与search-LWE问题的困难性是类似的，当然此步的归约过程一般是多项式尺寸的模q=poly(n)。

q=2，q=poly(n),q=exp，归约过程经历了这些发展。