格密码之LWE数学原理
-
参考文章:微信公众平台
-
在学习LWE问题的过程中,翻了不少博客和一些相关资料,发现不同资料对LWE问题与格困难问题的联系有不同的说法,有些文章把
LWE问题归约到SIS问题,而有些文章又是把LWE问题当作是CVP问题,这就导致我理解混乱LWE到底和格有什么关联,先简单说明一下我仔细思考后得到的结论(可能有些地方还有点错误):- 首先:
LWE本身是一个独立定义的计算困难性问题,它的基本形式就是带有小误差的模线性方程,从该定义出发只需要线性代数、模运算和概率论的一些知识就能学习LWE,如果进一步研究Ring-LWE,则需要学习抽象代数中的环、理想以及多项式环等知识。 - 其次:基于
LWE的加密方案,其密钥生成、加密和解密的过程一般都不需要显示构造格,也不需要调用LLL、BKZ等格算法。 - 与格的联系:
- LWE问题可以归约到格的困难性问题:
Regev建立了从某些最坏情况格问题到平均情况LWE问题的量子归约,结论具体描述为:如果存在一个能够高效解决平均情况下LWE实例的算法,那么我们就可以利用这个算法,构造出一个能够高效解决某些最坏情况下格问题的算法,也就是平均情况下的LWE问题最坏情况下的格问题,其中表示量子归约。- 在特定参数条件下,可以将
Decision-LWE归约到SIS,
- 对一些基于LWE问题提出的加密方案进行攻击,经常就是通过格的方法进行攻击的。
- LWE的一些攻击方法会利用
SIS类型的短向量问题。例如:Dual Attack中,攻击者通过寻找满足模约束的短向量,消去LWE样本中的秘密项,再利用误差分布的统计特征进行攻击。 - 可以将LWE问题转化为格上的解码问题,通常就与格中
BDD和CVP问题联系起来了。
- LWE的一些攻击方法会利用
- LWE问题可以归约到格的困难性问题:
- 首先:
-
所以,在学习LWE加密方案的时候其实没必要老是想着格,基于LWE加密解密的过程其实没有用到格相关的知识。
知识回顾
矩阵表示方程组
- 在学习线性代数和高等代数的时候我们一开始就需要了解矩阵。(当然某些编排不好的书一开始的内容就是行列式)。对于下面一个线性方程组,由于解方程的时候只有未知数前面的系数在改变,未知数的次数是不变的。
- 为了更方便书写,我们直接把线性方程组中的未知数省略掉,形成一个的矩阵,如果矩阵里面都是整数的话一般就是用表示这样的矩阵,如果这个矩阵里面的所有元素还要模,就使用表示模的的整数矩阵。
- 其中表示的是这个矩阵有行,也表示这个线性方程组中方程的个数。
- 其中表示的是这个矩阵有列,也表示这个线性方程组未知数的个数。
向量表示方程组
- 如下图所示的个向量的线性方程组,我们可以使用一个列向量来表示方程组中每个方程中相同未知数的系数。
- 对于那么对于上面这个方程组,分别使用列向量表示相同未知数前面的系数的集合,使用表示常数,那么方程组就可以使用向量更简单的表示出来:
矩阵乘法表示方程组
- 在学习了矩阵、向量、矩阵乘法之后,对于如下的一个线性方程组,其实可以使用矩阵乘法来表示出来。
- 可以使用一个的矩阵乘一个的矩阵,以及的矩阵表示这个线性方程组,如下所示:
LWE初步介绍
问题引入鸡兔同笼正常版
首先来看一下鸡兔同笼的问题,鸡兔同笼问题出自于《孙子算经》,具体问题如下:
1 | 有鸡、兔同笼,上有三十五头,下九十四足。问雉、兔各几何? |
- 我们可以使用穷举法,从0只鸡开始,然后一直到35只鸡,直到找到脚的数量符合题目的要求即可。
- 但是穷举法是偏离今天的
LWE的内容的,所以主要介绍的是另一种方法,也就是代数方法——解方程。首先确定位置量,鸡、兔的个数我们是不知道的,那就设鸡为,兔为,那么就可以列出如下的一个二元一次方程组:
- 将这个方程组使用矩阵表示就是如下的形式:
- 对于使用方程组的表示方法可以直接通过高斯消元法直接求出答案,而对于矩阵乘法表示可以通过左右两边乘一个左边方阵的逆矩阵,就可以得到结果。
问题引入鸡兔同笼误差版
- 对于上面的鸡兔同笼问题,我们做一个修改。这里我们假设,在数透和脚的数量的时候,存在一个误差,这个误差满足某个概率分布,这里我们就假设数脚我们多数了一个,这样就会变成下面的这个方程
- 此时我们不知道误差,所以我们列出的方程是这样的
- 这个时候如果再使用高斯消元法去求解这个方程,那就会得到下面这个解
- 这个结果出现了小数,显然是不正确的。因为存在一个误差值是我们所不知道的东西。
引入LWE问题
-
对于上面
鸡兔同笼误差版(方程组中的每个方程带误差,并且误差我们不知道),这就是这篇文章要说明的一个LWE问题。 -
LWE英文全称为learn with error,翻译过来为容错学习。容错学习的具体描述如下:- 设以及为整数(其中一般为质数),并设上的一个秘密向量,在上均匀选取矩阵,设为一个上的概率分布,且,并计算:
- 并给出,让我们还原出秘密向量,这就是最常见的
LWE问题(这种LWE问题也被称为搜索LWE问题,即Search-LWE)。
注解1:上面的,表示的是数域
q下的n维线性空间注解2:上面的,表示的是数域
q下的m×n矩阵,其维度是mn注解3:上面表示数域下的
m维线性空间存疑:这里留个疑问,对于LWE的问题具体是如何定义的需要去看看论文,LWE、MLWE如何定义的感觉会搞混掉。还有就是从问题的形式出发,就出现了Search-LWE和Decisional-LWE。目前就以上面的问题来定义LWE。(总之一般的LWE问题就是要我们求出e或者b,这两个知道其中一个就可以知道另一个。)

- 对于上述
LWE问题,如果使用高斯消元法进行求解就会扩大误差e的影响,使得求出的解与原来的解误差非常大。所以高斯消元法在LWE问题中就体现不出太大的作用。 - 这个时候如果我们知道的界限,我们就可以通过搜索,如果搜索到使得,其中B满足,这个时候我们就说找到了满足LWE问题的一组解。
理解LWE问题(抛弃)
-
这个部分需要调整一下,将移动到后面。
-
接下来将用几张图片,通过几何直观的感受来理解
LWE问题。在此之前,先来回顾一下格的定义:
- 在
LWE这个方程中,这个向量其实就是未知数,我们是不知道的,而是一个矩阵,结合上面的格的定义,我们就将这个矩阵拆分成个列向量,每个列向量有个元素。
- 假设这些列向量线性无关,那么这就构成了一个格,并且这个格的维数为
m,而这个格的秩为n,就以下面这个方程组做例子通过几何直观来理解吧:
- 对于上面的例子,格的基其实就是这两个列向量,接下来我们将这个格点画出来,并且将点使用不同颜色的点也标在图中。
- 注意:这里点其实并不是在格点上,此时结合LWE的求解(也就是通过搜索,如果搜索到使得,其中B满足,这个时候我们就说找到了满足LWE问题的一组解。)以及最近向量问题形式,我们不难发现Search-LWE问题其实本质上就是最近向量问题


- 从上图中我们可以看到,如果误差选取不好的话,就会出现多组解满足,并且目前除了搜索之外没有什么特别快的求解方案。
- 接下来再看一个图片,下面这张图片所出现的情况是误差向量非常大的时候,以误差向量的长度为半径画出一个圆,在这个圆内会有非常多的点,而这些点都满足,这就导致解不唯一,还需要我们在这些解中找到正确的解。

LWE困难问题
Search-LWE
对于Search-LWE问题,在LWE初步介绍那边已经介绍的相当清楚了,这里看情况看看要不要再讲一遍。
-
Search-LWE问题的描述这里在简单说一下:- 设,是素数,是上的一个分布,其中一般称为噪声分布。
-
还需要满足,当,需要满足;在实际使用中通常是在上的一个高斯分布。
-
接下来就是生成秘密,并生成随机矩阵以及误差向量,计算
-
并给出,让我们还原出秘密向量,这就是最常见的
LWE问题(这种LWE问题也被称为搜索LWE问题,即Search-LWE)。
-
-
Search-LWE问题是比较常见的一个LWE问题,在CTF中的很多题目基本上都是Search-LWE问题。 -
这里有一个关于
LWE的假设:假设Search-LWE问题是计算困难的,也就是:- 对于任何概率多项式算法
PPT algorithm, - 注意:其实实际应用中对假设的要求更严格,该假设是不能求出完整的,而实际中还要求不能求出部分的。
- 对于任何概率多项式算法
Decision-LWE
除了Search-LWE问题外,还有一个Decision-LWE问题,该问题并不是格中的CVP问题了,而是SVP问题。接下来需要具体介绍一下Decision-LWE的问题形式,以及其为什么是格中的SVP问题。
-
Decision-LWE问题是LWE问题的另一种形式,其中文翻译过来被叫做判定LWE问题。 -
D-LWE的核心是给定一组样本,判断这些样本究竟来自具有隐藏密码和噪声的LWE分布,还是来自均匀随机分布,具体的定义如下:-
设,是素数,是整数集合上的概率分布,从中随机抽样,是样本数量,是秘密向量。现在有如下两个分布:
-
分布一:
LWE分布- 生成一个秘密向量,随机生成,生成误差
- 计算出,此时就得到
-
分布二:均匀随机分布
- 从中随机选取 ;从中随机选取
- 这样从均匀随机分布中就得到了
-
有一个预言机,它会从
LWE分布中得到的数据和均匀随机分布得到的数据随机选择一组数据,让攻击者判断它选择的数据是来自带有秘密的LWE分布,还是没带有秘密的均匀随机分布。
-
-
对于
D-LWE问题,这边也有一个假设,也就是:- 对于任意的概率多项式算法,有
LWE数学结构
-
通过上面的介绍其实可以了解到,LWE其实就是在一些线性方程中添加一些错误,使得我们在不知道错误的情况下不能直接求解出线性方程的解,进而将秘密恢复出来。
-
在上面的初步介绍LWE问题,使用了线性方程组的例子,这算是最简单的代数结构形式的LWE问题;但是其他的代数结构其实也可以添加一些错误,使得我们无法求解,接下来我们就来介绍在其他代数结构上的LWE的操作过程,具体的有如下几个:
- 回顾线性方程组上的LWE,将其称为简化的LWE。
- 学习线性方程组带模的LWE,这个就是标准的LWE形式。
- 借助标准的LWE形式,将讨论
误差e在随机选取的时候,符合统计学的一些分布情况,以及误差e的大小如何选取。 - 借助标准的LWE形式,将讨论
秘密s的一些分布情况,比如秘密s可能只取值0、1,又或者值取值-1,0,1等情况。 - 借助标准的LWE形式,将讨论
样本a的一些分布情况(样本a实际上指的是s×n矩阵中的各个元素值),比如样本a存在线性关系,或者是样本a是由某个伪随机数生成器生成的。 - 学习在多项式上的LWE,称为
多项式LWE。(注意:这里的多项式是不构成环的多项式,构成环的多项式在下面会引入) - 学习在多项式环结构上的LWE,也被称为
Ring-LWE简称R-LWE。 - 学习在
Module-LWE,这个比较难理解,类似于矩阵里面的元素全是多项式环,秘密也由多项式环构成,误差也是多项式环,而Ring-LWE是Module-LWE的其中一种特例。
简化的LWE
-
首先对于简化的LWE,就是在线性方程组中上的每个方程添加错误,具体的形式如下:
- 设是正整数,其中有秘密向量,现在有一个矩阵,有误差向量
- 令,在已知的情况下,需要求出秘密向量
- 上面这个就是简化版本的
LWE问题。
-
对于简化版本的
LWE问题,由此可以形成一个LWE加密方案,具体的加密方案如下描述:- 设私钥很小,是小噪声向量,公钥,
- 加密一个整数消息的过程如下:
- 首先选取一个$r_{m×1}\in{0,1}^{m} e_{1_{}}\in \Z^{n}e_2 \in \Z$
- 加密过程,
- 解密过程:
- 由于,所以
- 将代入可以得到:
- 这样
- 当消息编码间隔大于噪声的界时,就能通过阈值摄入恢复出消息,其实就是
- 解密过程具体解释:
- 如果我们认为给字母做一个编码,比如
A编码成十进制数字0,B编码成十进制数字50、C编码成十进制数字100,以此类推下去,这样我们就形成了一个编码间隔等距为50的编码规则。 - 记
- 其中对于噪声来说,肯定会有一个界,当这个界小于编码间隔,在这个例子中,这里我们就取
- 此时如果编码是
A,也就是十进制的值为0,这样,如果是编码是,也就是十进制值为,这样 - 对于不同的字母,我们计算出的的结果是落在不同的区间内的并且这两个区间没有重叠部分,所以我们可以根据坐落在区间范围里面的值解码出不同的字母,从而对消息进行传递。
- 如果我们认为给字母做一个编码,比如
- 注意:这个无模的LWE加密其实不具备密码学安全性的,只是为了方便理解后续而进行讲解的。
-
主要说明一下关键元素的行列以及维数:
| 关键元素 | 维度 | 矩阵或行列向量 |
|---|---|---|
| A | m×n | 矩阵 |
| s | n×1 | 列向量 |
| e | m×1 | 列向量 |
| b=As+e | m×1 | 列向量 |
| r | m×1 | 列向量 |
| e1 | n×1 | 列向量 |
| e2 | 常数 |
例题1 Hello_LWE
- 下面来尝试一下这个题目:
1 | from sage.all import * |
例题2
例题3
标准的LWE
-
符号约定:
- 表示
模q的剩余类 - 表示范数
- 表示从集合中随机抽样
- 表示可忽略的函数
- 表示
-
回顾一下上面关于标准的LWE数学结构,并给出一些加密方案:
- 设,是素数,是上的一个分布,其中一般称为噪声分布。
- 还需要满足,当,需要满足;在实际使用中通常是在上的一个高斯分布。
- 接下来就是生成秘密,并生成随机矩阵以及误差向量
- 计算,最终公开,保留秘密。
-
LWE密钥加密:
-
密钥生成:给定一个安全的参数
n,输出一个密钥,其中 -
加密过程:
- 参数选择:输入密钥和消息,在中随机选取即,在中随机选取即
- 计算:
- 输出:和
-
解密过程:
- 使用密钥,以及密文对
- 计算:,并且定义\mu'=\cases{0,||b-\mathbf{as}||<\frac{q}{4}\\1, otherwise}
-
正确性:
-
安全性:
-
-
LWE公钥加密:
例题4_LWE High-Bits-Message
-
题目来源:
cryptohack -
题目附件如下:
1 | # dimension |
例题5_LWE Low-Bits-Message
- 题目来源:
cryptohack - 题目附件如下:
1 | # dimension |
误差e分布
- 对于误差的分布也是比较有讲究的,一般来说在实际上使用的时候通常就是采用高斯分布。
- 但是在
CTF题目中有的时候会改变误差的分布,使得题目中的LWE加密能够被破解,一般常见的分布如下:- 离散高斯分布:
- 均匀有界分布
- 中心二项分布:
- 二元分布:
- 稀疏分布
- 非对称分布
- 均匀模分布
秘密s分布与选取
- 对于秘密来说,
- 秘密是加解的密钥:此时秘密的选取基本上就是通过随机数进行选取,但是在
CTF题目可能会出一些随机数,或者说是像误差e分布那种题型。 - 秘密是传递的消息:此时秘密的选取要么就是使用者自定义的一个编码方式,要么就是将消息转换成二进制的形式形成一个或者多个
0、1向量。
- 秘密是加解的密钥:此时秘密的选取基本上就是通过随机数进行选取,但是在
样本a的分布
多项式LWE
Ring-LWE
前置知识
Polynomial—LWE
Polynomial-LWE其实指的就是多项式LWE,但是要和上面的多项式LWE区分开来,上面的多项式LWE是用于帮助理解Ring-LWE所讲述的前置知识。- 而
Ploynomial-LWE其实指的是多项式商环定义的LWE变体。

