• 参考文章:微信公众平台

  • 参考文章:格密码:LWE(Learning With Errors)

  • 参考文章:LWE – 三极管域 | Triode Field

  • 在学习LWE问题的过程中,翻了不少博客和一些相关资料,发现不同资料对LWE问题与格困难问题的联系有不同的说法,有些文章把LWE问题归约到SIS问题,而有些文章又是把LWE问题当作是CVP问题,这就导致我理解混乱LWE到底和格有什么关联,先简单说明一下我仔细思考后得到的结论(可能有些地方还有点错误):

    • 首先:LWE本身是一个独立定义的计算困难性问题,它的基本形式就是带有小误差的模线性方程,从该定义出发只需要线性代数、模运算和概率论的一些知识就能学习LWE,如果进一步研究Ring-LWE,则需要学习抽象代数中的环、理想以及多项式环等知识。
    • 其次:基于LWE的加密方案,其密钥生成、加密和解密的过程一般都不需要显示构造格,也不需要调用LLL、BKZ等格算法。
    • 与格的联系:
      • LWE问题可以归约到格的困难性问题:
        1. Regev建立了从某些最坏情况格问题到平均情况LWE问题的量子归约,结论具体描述为:如果存在一个能够高效解决平均情况下LWE实例的算法,那么我们就可以利用这个算法,构造出一个能够高效解决某些最坏情况下格问题的算法,也就是平均情况下的LWE问题≥Q≥_Q最坏情况下的格问题,其中≥Q≥_Q表示量子归约。
        2. 在特定参数条件下,可以将Decision-LWE归约到SIS,
      • 对一些基于LWE问题提出的加密方案进行攻击,经常就是通过格的方法进行攻击的。
        1. LWE的一些攻击方法会利用SIS类型的短向量问题。例如:Dual Attack中,攻击者通过寻找满足模约束的短向量,消去LWE样本中的秘密项,再利用误差分布的统计特征进行攻击。
        2. 可以将LWE问题转化为格上的解码问题,通常就与格中BDD和CVP问题联系起来了。
  • 所以,在学习LWE加密方案的时候其实没必要老是想着格,基于LWE加密解密的过程其实没有用到格相关的知识。

知识回顾

矩阵表示方程组

  • 在学习线性代数和高等代数的时候我们一开始就需要了解矩阵。(当然某些编排不好的书一开始的内容就是行列式)。对于下面一个线性方程组,由于解方程的时候只有未知数前面的系数在改变,未知数的次数是不变的。

{a11x1+a12x2+...+a1nxn=b1a21x1+a22x2+...+a2nxn=b2      ⋮             ⋮                    ⋮      ⋮as1x1+as2x2+...+asnxn=bs\begin{cases} a_{11}x_1+a_{12}x_2+...+a_{1n}x_n &= b_1 \\ a_{21}x_1+a_{22}x_2+...+a_{2n}x_n &= b_2\\ ~~~~~~\vdots~~~~~~~~~~~~~\vdots~~~~~~~~~~~~~~~~~~~~\vdots&~~~~~~\vdots\\ a_{s1}x_1+a_{s2}x_2+...+a_{sn}x_n&=b_s \end{cases}

  • 为了更方便书写,我们直接把线性方程组中的未知数省略掉,形成一个s×ns×n的矩阵,如果矩阵里面都是整数的话一般就是用Zs×n\Z^{s×n}表示这样的矩阵,如果这个矩阵里面的所有元素还要模qq,就使用Zqs×n\Z^{s×n}_{q}表示模qq的s×ns×n的整数矩阵。
    • 其中ss表示的是这个矩阵有ss行,也表示这个线性方程组中方程的个数。
    • 其中nn表示的是这个矩阵有nn列,也表示这个线性方程组未知数的个数。

[a11a12…a1na21a22…a2n⋮⋮⋱⋮as1as2…asn]s×n\begin{bmatrix} a_{11} & a_{12} & \dots & a_{1n} \\ a_{21} & a_{22} & \dots & a_{2n} \\ \vdots & \vdots & \ddots& \vdots \\ a_{s1} & a_{s2} & \dots & a_{sn} \end{bmatrix}_{s×n}

向量表示方程组

  • 如下图所示的个向量的线性方程组,我们可以使用一个列向量来表示方程组中每个方程中相同未知数的系数。

{a11x1+a12x2+...+a1nxn=b1a21x1+a22x2+...+a2nxn=b2      ⋮             ⋮                    ⋮      ⋮as1x1+as2x2+...+asnxn=bs\begin{cases} a_{11}x_1+a_{12}x_2+...+a_{1n}x_n &= b_1 \\ a_{21}x_1+a_{22}x_2+...+a_{2n}x_n &= b_2\\ ~~~~~~\vdots~~~~~~~~~~~~~\vdots~~~~~~~~~~~~~~~~~~~~\vdots&~~~~~~\vdots\\ a_{s1}x_1+a_{s2}x_2+...+a_{sn}x_n&=b_s \end{cases}

  • 对于那么对于上面这个方程组,分别使用列向量α1,...,αn\alpha_1,...,\alpha_n表示相同未知数前面的系数的集合,使用β\beta表示常数,那么方程组就可以使用向量更简单的表示出来:

α1=(a11a21...as1),....,αn=(a1na2n...asn),β=(b1b2...bs)x1α1+.....+xnαn=β\alpha_1=\begin{pmatrix} a_{11} \\ a_{21} \\ ... \\ a_{s1} \end{pmatrix},...., \alpha_n=\begin{pmatrix} a_{1n} \\ a_{2n} \\ ... \\ a_{sn} \end{pmatrix} ,\beta=\begin{pmatrix} b_{1} \\ b_{2} \\ ... \\ b_{s} \end{pmatrix} \\ \\ x_1\alpha_1+.....+x_n\alpha_n=\beta

矩阵乘法表示方程组

  • 在学习了矩阵、向量、矩阵乘法之后,对于如下的一个线性方程组,其实可以使用矩阵乘法来表示出来。

{a11x1+a12x2+...+a1nxn=b1a21x1+a22x2+...+a2nxn=b2      ⋮             ⋮                    ⋮      ⋮as1x1+as2x2+...+asnxn=bs\begin{cases} a_{11}x_1+a_{12}x_2+...+a_{1n}x_n &= b_1 \\ a_{21}x_1+a_{22}x_2+...+a_{2n}x_n &= b_2\\ ~~~~~~\vdots~~~~~~~~~~~~~\vdots~~~~~~~~~~~~~~~~~~~~\vdots&~~~~~~\vdots\\ a_{s1}x_1+a_{s2}x_2+...+a_{sn}x_n&=b_s \end{cases}

  • 可以使用一个s×ns×n的矩阵乘一个n×1n×1的矩阵,以及s×1s×1的矩阵表示这个线性方程组,如下所示:

[a11a12…a1na21a22…a2n⋮⋮⋱⋮as1as2…asn]s×n×[x1x2⋮xn]n×1=[b1b2⋮bs]\begin{bmatrix} a_{11} & a_{12} & \dots & a_{1n} \\ a_{21} & a_{22} & \dots & a_{2n} \\ \vdots & \vdots & \ddots& \vdots \\ a_{s1} & a_{s2} & \dots & a_{sn} \end{bmatrix}_{s×n}× \begin{bmatrix} x_{1} \\ x_{2} \\ \vdots \\ x_{n} \end{bmatrix}_{n×1}=\begin{bmatrix} b_{1} \\ b_{2} \\ \vdots \\ b_{s} \end{bmatrix}

LWE初步介绍

问题引入鸡兔同笼正常版

首先来看一下鸡兔同笼的问题,鸡兔同笼问题出自于《孙子算经》,具体问题如下:

1
有鸡、兔同笼,上有三十五头,下九十四足。问雉、兔各几何?
  • 我们可以使用穷举法,从0只鸡开始,然后一直到35只鸡,直到找到脚的数量符合题目的要求即可。
  • 但是穷举法是偏离今天的LWE的内容的,所以主要介绍的是另一种方法,也就是代数方法——解方程。首先确定位置量,鸡、兔的个数我们是不知道的,那就设鸡为x1x_1,兔为x2x_2,那么就可以列出如下的一个二元一次方程组:

{x1+x2=352x1+4x2=94\begin{cases} x_1+x_2&= 35 \\ 2x_1+4x_2&= 94\\ \end{cases}

  • 将这个方程组使用矩阵表示就是如下的形式:

[1124]2×2×[x1x2]2×1=[3594]\begin{bmatrix} 1 & 1 \\ 2 & 4 \\ \end{bmatrix}_{2×2}×\begin{bmatrix} x_{1} \\ x_{2} \\ \end{bmatrix}_{2×1}=\begin{bmatrix} 35 \\ 94 \\ \end{bmatrix}

  • 对于使用方程组的表示方法可以直接通过高斯消元法直接求出答案,而对于矩阵乘法表示可以通过左右两边乘一个左边方阵的逆矩阵,就可以得到结果。

问题引入鸡兔同笼误差版

  • 对于上面的鸡兔同笼问题,我们做一个修改。这里我们假设,在数透和脚的数量的时候,存在一个误差,这个误差满足某个概率分布,这里我们就假设数脚我们多数了一个,这样就会变成下面的这个方程

{x1+x2+e1=352x1+4x2+e2=95\begin{cases} x_1+x_2+e_1&= 35 \\ 2x_1+4x_2+e_2&= 95\\ \end{cases}

  • 此时我们不知道误差,所以我们列出的方程是这样的

{x1′+x2′=352x1′+4x2′=95\begin{cases} x_1'+x_2'&= 35 \\ 2x_1'+4x_2'&= 95\\ \end{cases}

  • 这个时候如果再使用高斯消元法去求解这个方程,那就会得到下面这个解

{x1′=22.5x2′=12.5\begin{cases} x_1'= 22.5 \\ x_2'= 12.5\\ \end{cases}

  • 这个结果出现了小数,显然是不正确的。因为存在一个误差值e′=x−x′e'=x-x'是我们所不知道的东西。

引入LWE问题

  • 对于上面鸡兔同笼误差版(方程组中的每个方程带误差,并且误差我们不知道),这就是这篇文章要说明的一个LWE问题。

  • LWE英文全称为learn with error,翻译过来为容错学习。容错学习的具体描述如下:

    • 设n,mn,m以及qq为整数(其中qq一般为质数),并设s∈Zqn\mathbf{s}\in \Z_q^n上的一个秘密向量,在Zqm×n\Z_q^{m×n}上均匀选取矩阵A\mathbf{A},设χ\chi为一个Zm\Z^m上的概率分布,且e←χe\leftarrow \chi,并计算:

    b=As+e mod( q)\mathbf{b}=\mathbf{As}+\mathbf{e}~mod(~q)

    • 并给出(A,b)(\mathbf{A},\mathbf{b}),让我们还原出秘密向量s\mathbf{s},这就是最常见的LWE问题(这种LWE问题也被称为搜索LWE问题,即Search-LWE)。

注解1:上面的Zqn\Z_q^n,表示的是数域q下的n维线性空间

注解2:上面的Zqm×n\Z_q^{m×n},表示的是数域q下的m×n矩阵,其维度是mn

注解3:上面Zm\Z^m表示数域Z\Z下的m维线性空间

存疑:这里留个疑问,对于LWE的问题具体是如何定义的需要去看看论文,LWE、MLWE如何定义的感觉会搞混掉。还有就是从问题的形式出发,就出现了Search-LWE和Decisional-LWE。目前就以上面的问题来定义LWE。(总之一般的LWE问题就是要我们求出e或者b,这两个知道其中一个就可以知道另一个。)

image-20251118214027379

  • 对于上述LWE问题,如果使用高斯消元法进行求解就会扩大误差e的影响,使得求出的解与原来的解误差非常大。所以高斯消元法在LWE问题中就体现不出太大的作用。
  • 这个时候如果我们知道ee的界限,我们就可以通过搜索s′∈Zqn\mathbf{s'}\in\Z^n_q,如果搜索到s′∈Zqn\mathbf{s'}\in\Z^n_q使得∣∣As′−b∣∣∞≤B||\mathbf{As'}-\mathbf{b}||_{\infty}≤B,其中B满足∣∣e∣∣∞≤B||\mathbf{e}||_{\infty}≤B,这个时候我们就说找到了满足LWE问题的一组解。

理解LWE问题(抛弃)

  • 这个部分需要调整一下,将移动到后面。

  • 接下来将用几张图片,通过几何直观的感受来理解LWE问题。在此之前,先来回顾一下格的定义:

L(B)={∑i=1nxibi:xi∈Z,i=1,...,n}L(\mathbf{B})=\{\sum^{n}_{i=1}x_ib_i:x_i\in Z,i=1,...,n\}

  • 在LWE这个方程中,sn×1s_{n×1}这个向量其实就是未知数,我们是不知道的,而Am×nA_{m×n}是一个矩阵,结合上面的格的定义,我们就将这个矩阵Am×nA_{m×n}拆分成nn个列向量,每个列向量有mm个元素。

Am×n=(α1,...,αn)A_{m×n}=(\alpha_1,...,\alpha_n)

  • 假设这些列向量线性无关,那么这(α1,...,αn)(\alpha_1,...,\alpha_n)就构成了一个格,并且这个格的维数为m,而这个格的秩为n,就以下面这个方程组做例子通过几何直观来理解吧:

{x1+x2+0=102x1+4x2+1=27\begin{cases} x_1+x_2+0&= 10 \\ 2x_1+4x_2+1&= 27\\ \end{cases}

{x1′+x2′=102x1′+4x2′=27\begin{cases} x_1'+x_2'&= 10 \\ 2x_1'+4x_2'&= 27 \\ \end{cases}

[1124]2×2×[x1′x2′]n×1=[1027]\begin{bmatrix} 1 & 1 \\ 2 & 4 \\ \end{bmatrix}_{2×2}×\begin{bmatrix} x_{1}' \\ x_{2}' \\ \end{bmatrix}_{n×1}=\begin{bmatrix} 10 \\ 27 \\ \end{bmatrix}

  • 对于上面的例子,格的基其实就是这两个列向量α1=(1,2)T,α2=(1,4)T\alpha_1=(1,2)^{T},\alpha_2=(1,4)^{T},接下来我们将这个格点画出来,并且将点(10,27)(10,27)使用不同颜色的点也标在图中。
  • 注意:这里点(10,27)(10,27)其实并不是在格点上,此时结合LWE的求解(也就是通过搜索s′∈Zqn\mathbf{s'}\in\Z^n_q,如果搜索到s′∈Zqn\mathbf{s'}\in\Z^n_q使得∣∣As′−b∣∣∞≤B||\mathbf{As'}-\mathbf{b}||_{\infty}≤B,其中B满足∣∣e∣∣∞≤B||\mathbf{e}||_{\infty}≤B,这个时候我们就说找到了满足LWE问题的一组解。)以及最近向量问题形式,我们不难发现Search-LWE问题其实本质上就是最近向量问题

image-20251118232126864

image-20251119105804122

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

​ image-20251121110842335

LWE困难问题

Search-LWE

对于Search-LWE问题,在LWE初步介绍那边已经介绍的相当清楚了,这里看情况看看要不要再讲一遍。

  • Search-LWE问题的描述这里在简单说一下:

    • 设n,m∈Nn,m \in N,qq是素数,χ\chi是Z/qZ\Z/q\Z上的一个分布,其中χ\chi一般称为噪声分布。
  • χ\chi还需要满足,当e←χe\leftarrow \chi,ee需要满足∣∣e∣∣≤B<<q||e||≤B<<q;在实际使用中χ\chi通常是在Z\Z上的一个高斯分布。

    • 接下来就是生成秘密s∈Zqns\in \Z^{n}_q,并生成随机矩阵A∈Zqm×nA\in \Z^{m×n}_q以及误差向量e←χme\leftarrow \chi ^{m},计算b=As+e mod( q)b = As+e~mod(~q)

    • 并给出(A,b)(\mathbf{A},\mathbf{b}),让我们还原出秘密向量s\mathbf{s},这就是最常见的LWE问题(这种LWE问题也被称为搜索LWE问题,即Search-LWE)。

  • Search-LWE问题是比较常见的一个LWE问题,在CTF中的很多题目基本上都是Search-LWE问题。

  • 这里有一个关于LWE的假设:假设Search-LWE问题是计算困难的,也就是Search LWEn,q,χ assumptionSearch~LWE_{n,q,\chi}~assumption:

    • 对于任何概率多项式算法PPT algorithmA\Alpha,Prs←Zqn[AOsn(1n)=s]=negl(n)Pr_{s\leftarrow \Z^{n}_{q}}[A^{O^{n}_{s}}(1^{n})=s]=negl(n)
    • 注意:其实实际应用中对假设的要求更严格,该假设是不能求出完整的ss,而实际中还要求不能求出部分的ss。

Decision-LWE

除了Search-LWE问题外,还有一个Decision-LWE问题,该问题并不是格中的CVP问题了,而是SVP问题。接下来需要具体介绍一下Decision-LWE的问题形式,以及其为什么是格中的SVP问题。

  • Decision-LWE问题是LWE问题的另一种形式,其中文翻译过来被叫做判定LWE问题。

  • D-LWE的核心是给定一组样本,判断这些样本究竟来自具有隐藏密码和噪声的LWE分布,还是来自均匀随机分布,具体的定义如下:

    • 设n∈Nn\in N,qq是素数,χ\chi是整数集合Z\Z上的概率分布,ee从χ\chi中随机抽样,mm是样本数量,s∈Zqns\in \Z^{n}_q是秘密向量。现在有如下两个分布:

    • 分布一:LWE分布

      • 生成一个秘密向量ss,随机生成ai∈Zqn,i=1,2,...a_i \in Z^{n}_q,i=1,2,...,生成误差ei,i=1,2,....e_i,i=1,2,....
      • 计算出bi=ais+eib_i=a_is+e_i,此时就得到(ai,bi)(\mathbf{a}_i,b_i)
    • 分布二:均匀随机分布

      • 从Zqn\Z^{n}_q中随机选取ai′,i=1,2,...a'_i,i=1,2,... ;从Zq\Z_q中随机选取bi′,i=1,2,....b'_i,i=1,2,....
      • 这样从均匀随机分布中就得到了(ai′,bi′)(\mathbf{a'_i},b'_i)
    • 有一个预言机,它会从LWE分布中得到的数据(ai,bi)(\mathbf{a_i},b_i)和均匀随机分布得到的数据(ai′,bi′)(\mathbf{a'_i},b'_i)随机选择一组数据,让攻击者判断它选择的数据是来自带有秘密的LWE分布,还是没带有秘密的均匀随机分布。

  • 对于D-LWE问题,这边也有一个假设,也就是Decisional LWEn,q,χ assumptionDecisional~LWE_{n,q,\chi}~assumption:

    • 对于任意的概率多项式算法A\Alpha,有∣Pr[AOsn(1n)=1]−Pr[AR(1n)=1]∣=negl(n)|Pr[\Alpha^{O^{n}_{s}}(1^{n})=1]-Pr[A^{R}(1^{n})=1]|=negl(n)

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,就是在线性方程组中上的每个方程添加错误,具体的形式如下:

    • 设m、nm、n是正整数,其中有秘密向量s=(s1,s2,...,sm)∈Zns=(s_1,s_2,...,s_m)\in \Z^{n},现在有一个矩阵A∈Zm×nA\in \Z^{m×n},有误差向量e=(e1,e2,...,en)∈Zme =(e_1,e_2,...,e_n)\in \Z^{m}
    • 令b=As+eb=As+e,在已知(A,b)(A,b)的情况下,需要求出秘密向量ss
    • 上面这个就是简化版本的LWE问题。
  • 对于简化版本的LWE问题,由此可以形成一个LWE加密方案,具体的加密方案如下描述:

    • 设私钥sn×1∈Zns_{n×1}\in \Z^{n}很小,em×1e_{m×1}是小噪声向量,公钥A∈Zm×nA \in \Z^{m×n},bm×1=Am×nsn×1+em×1b_{m×1} = A_{m×n}s_{n×1}+e_{m×1}
    • 加密一个整数消息MM的过程如下:
      • 首先选取一个$r_{m×1}\in{0,1}^{m} ,并选取噪声向量,并选取噪声向量e_{1_{}}\in \Z^{n}以及选取噪声整数以及选取噪声整数e_2 \in \Z$
      • 加密过程c1n×1=Am×nTrm×1+e1n×1c_{1_{n×1}}=A_{m×n}^{T}r_{m×1}+e_{1_{n×1}}, c2=bm×1Trm×1+e2+Mc_2=b_{m×1}^{T}r_{m×1}+e_2+M
    • 解密过程:
      • 由于b=As+eb=As+e,所以bT=sTAT+eTb^{T}=s^{T}A^{T}+e^{T}
      • c2−sTc1=bTr+e2+M−sTATr−sTe1c_2-s^{T}c_1=b^{T}r+e_2+M-s^{T}A^{T}r-s^{T}e_1
      • 将bT=sTAT+eTb^{T}=s^{T}A^{T}+e^{T}代入可以得到:sTATr+eTr+e2+M−sTATr−sTe1s^{T}A^{T}r+e^{T}r+e_2+M-s^{T}A^{T}r-s^{T}e_1
      • 这样c2−sTc1=eTr+e2+M−sTe1c_2-s^{T}c_1=e^{T}r+e_2+M-s^{T}e_1
      • 当消息编码间隔大于噪声的界时,就能通过阈值摄入恢复出消息MM,其实就是
    • 解密过程具体解释:
      • 如果我们认为给字母做一个编码,比如A编码成十进制数字0,B编码成十进制数字50、C编码成十进制数字100,以此类推下去,这样我们就形成了一个编码间隔等距为50的编码规则。
      • 记v=c2−sTc1=eTr+e2+M−sTe1=M+noisev=c_2-s^{T}c_1=e^{T}r+e_2+M-s^{T}e_1=M+noise
      • 其中对于噪声来说,肯定会有一个界∣noise∣≤α|noise|≤\alpha,当这个界α\alpha小于编码间隔,在这个例子中α<50\alpha < 50,这里我们就取α=10\alpha = 10
      • 此时如果编码MM是A,也就是MM十进制的值为0,这样M+noise∈[−10,10]M+noise \in [-10,10],如果是编码MM是BB,也就是MM十进制值为5050,这样M+noise∈[40,50]M+noise \in [40,50]
      • 对于不同的字母,我们计算出的v=c2−sTc1v=c_2-s^{T}c_1的结果是落在不同的区间内的并且这两个区间没有重叠部分,所以我们可以根据坐落在区间范围里面的cc值解码出不同的字母,从而对消息进行传递。
    • 注意:这个无模的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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
from sage.all import *
import string
import random
import hashlib

strings = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
flag = "flag{"
md5 = hashlib.md5()
# 定义秘密向量的维数n,也就是私钥的维数n
n = 10
# 定义错误向量的维数m,也就是私钥的维数m
m = 12
# 定义噪声和随机数的上界
B = 100

# 随机生成flag
for i in range(30):
flag += random.choice(strings)
flag += "}"
# 计算flag的哈希值
md5.update(flag.encode("utf-8"))
#print(md5.hexdigest())
strings = strings + "{}"

# 对字符串进行编码操作,消息码的距离为5000
message_dict = dict()
for i in range(len(strings)):
message_dict.update({strings[i]:5000*i})


# 加密过程
# 先随机生成出私钥等加密过程必须的量
s = random_vector(ZZ,n,x=0,y=200).column()
e = random_vector(ZZ,m,x=0,y=B).column()
r = random_vector(ZZ,m,x=0,y=2).column()
e1 = random_vector(ZZ,n,x=0,y=B).column()
e2 = random.randint(0,B)
A = random_matrix(ZZ,m,n,x=1,y=1000)
b = A*s + e


# 对每个字符串进行加密操作
c1 = []
c2 = []
A_T = A.transpose()
b_T = b.transpose()

for i in flag:
M = message_dict.get(i)
c1.append(A_T*r+e1)
c2.append(b_T*r+e2+M)

print("c1 =",c1)
print("c2 =",c2)
# 泄露公钥、私钥
print("A =",A)
print("b =",b)
print("s =",s)
# 输出flag的哈希值
print(md5.hexdigest())

c1 = [[(3187), (2895), (3230), (1552), (2673), (2958), (3329), (2782), (3258), (1268)], [(3187), (2895), (3230), (1552), (2673), (2958), (3329), (2782), (3258), (1268)], [(3187), (2895), (3230), (1552), (2673), (2958), (3329), (2782), (3258), (1268)], [(3187), (2895), (3230), (1552), (2673), (2958), (3329), (2782), (3258), (1268)], [(3187), (2895), (3230), (1552), (2673), (2958), (3329), (2782), (3258), (1268)], [(3187), (2895), (3230), (1552), (2673), (2958), (3329), (2782), (3258), (1268)], [(3187), (2895), (3230), (1552), (2673), (2958), (3329), (2782), (3258), (1268)], [(3187), (2895), (3230), (1552), (2673), (2958), (3329), (2782), (3258), (1268)], [(3187), (2895), (3230), (1552), (2673), (2958), (3329), (2782), (3258), (1268)], [(3187), (2895), (3230), (1552), (2673), (2958), (3329), (2782), (3258), (1268)], [(3187), (2895), (3230), (1552), (2673), (2958), (3329), (2782), (3258), (1268)], [(3187), (2895), (3230), (1552), (2673), (2958), (3329), (2782), (3258), (1268)], [(3187), (2895), (3230), (1552), (2673), (2958), (3329), (2782), (3258), (1268)], [(3187), (2895), (3230), (1552), (2673), (2958), (3329), (2782), (3258), (1268)], [(3187), (2895), (3230), (1552), (2673), (2958), (3329), (2782), (3258), (1268)], [(3187), (2895), (3230), (1552), (2673), (2958), (3329), (2782), (3258), (1268)], [(3187), (2895), (3230), (1552), (2673), (2958), (3329), (2782), (3258), (1268)], [(3187), (2895), (3230), (1552), (2673), (2958), (3329), (2782), (3258), (1268)], [(3187), (2895), (3230), (1552), (2673), (2958), (3329), (2782), (3258), (1268)], [(3187), (2895), (3230), (1552), (2673), (2958), (3329), (2782), (3258), (1268)], [(3187), (2895), (3230), (1552), (2673), (2958), (3329), (2782), (3258), (1268)], [(3187), (2895), (3230), (1552), (2673), (2958), (3329), (2782), (3258), (1268)], [(3187), (2895), (3230), (1552), (2673), (2958), (3329), (2782), (3258), (1268)], [(3187), (2895), (3230), (1552), (2673), (2958), (3329), (2782), (3258), (1268)], [(3187), (2895), (3230), (1552), (2673), (2958), (3329), (2782), (3258), (1268)], [(3187), (2895), (3230), (1552), (2673), (2958), (3329), (2782), (3258), (1268)], [(3187), (2895), (3230), (1552), (2673), (2958), (3329), (2782), (3258), (1268)], [(3187), (2895), (3230), (1552), (2673), (2958), (3329), (2782), (3258), (1268)], [(3187), (2895), (3230), (1552), (2673), (2958), (3329), (2782), (3258), (1268)], [(3187), (2895), (3230), (1552), (2673), (2958), (3329), (2782), (3258), (1268)], [(3187), (2895), (3230), (1552), (2673), (2958), (3329), (2782), (3258), (1268)], [(3187), (2895), (3230), (1552), (2673), (2958), (3329), (2782), (3258), (1268)], [(3187), (2895), (3230), (1552), (2673), (2958), (3329), (2782), (3258), (1268)], [(3187), (2895), (3230), (1552), (2673), (2958), (3329), (2782), (3258), (1268)], [(3187), (2895), (3230), (1552), (2673), (2958), (3329), (2782), (3258), (1268)], [(3187), (2895), (3230), (1552), (2673), (2958), (3329), (2782), (3258), (1268)]]
c2 = [[3519190], [3549190], [3494190], [3524190], [3754190], [3584190], [3694190], [3704190], [3569190], [3524190], [3544190], [3569190], [3529190], [3564190], [3609190], [3639190], [3744190], [3589190], [3564190], [3744190], [3664190], [3709190], [3589190], [3514190], [3554190], [3749190], [3714190], [3609190], [3589190], [3504190], [3694190], [3559190], [3604190], [3714190], [3674190], [3759190]]
A = [(608, 878, 168, 835, 154, 120, 530, 656, 125, 79), (991, 289, 475, 884, 42, 77, 979, 83, 148, 605), (621, 630, 371, 372, 238, 664, 218, 271, 495, 895), (438, 558, 512, 283, 105, 558, 24, 813, 80, 354), (178, 605, 565, 207, 125, 228, 873, 878, 545, 288), (343, 170, 248, 610, 710, 412, 912, 227, 323, 273), (954, 401, 667, 195, 714, 325, 289, 103, 505, 106), (878, 865, 652, 208, 866, 615, 686, 693, 622, 229), (636, 805, 382, 182, 592, 931, 602, 584, 751, 364), (351, 159, 910, 587, 549, 458, 314, 390, 192, 392), (472, 212, 943, 667, 332, 805, 802, 440, 827, 204), (8, 789, 370, 655, 681, 2, 786, 466, 531, 496)]
b = [(547070), (666345), (595648), (483896), (611643), (568355), (582317), (810385), (702445), (611032), (787350), (631299)]
s = [(175), (18), (166), (174), (132), (35), (120), (199), (173), (144)]
a97399bdd05abc8c0bda3c8170c72e8b

例题2

例题3

标准的LWE

  • 符号约定:

    • Z/qZ\Z/q\Z表示模q的剩余类
    • ∣∣⋅∣∣||·||表示L2L2范数
    • s←Ss\leftarrow S表示ss从集合SS中随机抽样
    • negl(⋅)negl(·)表示可忽略的函数
  • 回顾一下上面关于标准的LWE数学结构,并给出一些加密方案:

    • 设n,m∈Nn,m \in N,qq是素数,χ\chi是Z/qZ\Z/q\Z上的一个分布,其中χ\chi一般称为噪声分布。
    • χ\chi还需要满足,当e←χe\leftarrow \chi,ee需要满足∣∣e∣∣≤B<<q||e||≤B<<q;在实际使用中χ\chi通常是在Z\Z上的一个高斯分布。
    • 接下来就是生成秘密s∈Zqns\in \Z^{n}_q,并生成随机矩阵A∈Zqm×nA\in \Z^{m×n}_q以及误差向量e←χme\leftarrow \chi ^{m}
    • 计算b=As+e mod( q)b = As+e~mod(~q),最终公开(A,b)(A,b),保留秘密ss。
  • LWE密钥加密:

    • 密钥生成:给定一个安全的参数n,输出一个密钥sksk,其中sk=s←Zqnsk=\mathbf{s}\leftarrow \Z^{n}_q

    • 加密过程:

      • 参数选择:输入密钥ss和消息μ∈{0,1}\mu \in \{0,1\},在Zqn\Z^{n}_q中随机选取a\mathbf{a}即a←Zqna\leftarrow \Z^{n}_q,在χ\chi中随机选取ee即e←χe\leftarrow \chi
      • 计算:b=as+e+μ⋅⌈q2⌉ mod( q)b= \mathbf{as}+e+\mu·\lceil \frac{q}{2} \rceil ~mod(~q)
      • 输出:a\mathbf{a}和bb
    • 解密过程:

      • 使用密钥s\mathbf{s},以及密文对(a,b)(\mathbf{a},b)
      • 计算:μ′=(b−ab−e)⌈q2⌉−1mod( q)\mu'= (b-\mathbf{ab}-e)\lceil \frac{q}{2}\rceil^{-1} mod(~q),并且定义\mu'=\cases{0,||b-\mathbf{as}||<\frac{q}{4}\\1, otherwise}
    • 正确性:

    • 安全性:

  • LWE公钥加密:

例题4_LWE High-Bits-Message

  • 题目来源:cryptohack

  • 题目附件如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# dimension
n = 64
# plaintext modulus
p = 257
# ciphertext modulus
q = 0x10001
# bound for error term
error_bound = int(floor((q/p)/2))
# message scaling factor
delta = int(round(q/p))


V = VectorSpace(GF(q), n)
S = V.random_element()
print("S = ", S, "\n")

m = ?

A = V.random_element()
error = randint(-error_bound, error_bound)
b = A * S + m * delta + error

print("A = ", A)
print("b = ", b)

S = (55542, 19411, 34770, 6739, 63198, 63821, 5900, 32164, 51223, 38979, 24459, 10936, 17256, 20215, 35814, 42905, 53656, 17000, 1834, 51682, 43780, 22391, 33012, 61667, 37447, 16404, 58991, 61772, 44888, 43199, 32039, 26885, 17206, 62186, 58387, 57048, 38393, 29306, 58001, 57199, 33472, 56572, 53429, 62593, 14134, 40522, 25106, 34325, 37646, 43688, 14259, 24197, 33427, 43977, 18322, 38877, 55093, 12466, 16869, 25413, 54773, 59532, 62694, 13948)

A = (13759, 12750, 38163, 63722, 39130, 22935, 58866, 48803, 15933, 64995, 60517, 64302, 42432, 32000, 22058, 58123, 53993, 33790, 35783, 61333, 53431, 43016, 60795, 25781, 28091, 11212, 64592, 11385, 24690, 40658, 35307, 63583, 60365, 60359, 32568, 35417, 22078, 38207, 16331, 53636, 28734, 30436, 18170, 15939, 966, 48519, 41621, 36371, 41836, 4026, 33536, 57062, 52428, 59850, 476, 43354, 61614, 32243, 42518, 19733, 63464, 29357, 56039, 15013)
b = 44007

例题5_LWE Low-Bits-Message

  • 题目来源:cryptohack
  • 题目附件如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# dimension
n = 64
# plaintext modulus
p = 257
# ciphertext modulus
q = 0x10001
# bound for error term
error_bound = int(floor((q/p)/2))


V = VectorSpace(GF(q), n)
S = V.random_element()
print("S = ", S, "\n")

m = ?

A = V.random_element()
error = randint(-error_bound, error_bound)
b = A * S + error * p + m

print("A = ", A)
print("b = ", b)



S = (10082, 48747, 17960, 55638, 37012, 51876, 10128, 37750, 7608, 58952, 33296, 25463, 38900, 85, 65248, 42153, 44966, 31594, 40676, 56828, 30325, 38502, 65083, 7497, 2667, 54022, 24029, 32162, 57267, 12253, 6668, 5181, 14906, 51655, 61347, 4722, 22227, 23606, 63183, 52860, 1670, 31085, 42633, 47197, 7255, 16150, 9574, 62956, 26742, 57998, 49467, 31224, 60073, 12730, 41419, 41042, 53032, 16339, 32913, 16351, 34283, 47845, 3617, 35718)

A = (53751, 21252, 55954, 16345, 60990, 2822, 56279, 37048, 36153, 52141, 2121, 56565, 48112, 43755, 12951, 22539, 29478, 28421, 62175, 10265, 36378, 21305, 42402, 26359, 939, 60690, 1161, 65097, 34505, 19777, 29652, 42868, 49148, 38296, 31916, 25606, 18700, 12655, 35631, 64674, 29018, 21021, 14865, 40196, 14036, 40278, 37209, 35585, 34344, 33030, 285, 58536, 56121, 40899, 24262, 62326, 57433, 5765, 24456, 28859, 45170, 14799, 21567, 55484)
b = 11507

误差e分布

  • 对于误差ee的分布也是比较有讲究的,一般来说在实际上使用的时候ee通常就是采用高斯分布。
  • 但是在CTF题目中有的时候会改变误差ee的分布,使得题目中的LWE加密能够被破解,一般常见的分布如下:
    • 离散高斯分布:
    • 均匀有界分布
    • 中心二项分布:
    • 二元分布:
    • 稀疏分布
    • 非对称分布
    • 均匀模分布

秘密s分布与选取

  • 对于秘密ss来说,
    • 秘密ss是加解的密钥:此时秘密ss的选取基本上就是通过随机数进行选取,但是在CTF题目可能会出一些随机数,或者说是像误差e分布那种题型。
    • 秘密ss是传递的消息:此时秘密ss的选取要么就是使用者自定义的一个编码方式,要么就是将消息转换成二进制的形式形成一个或者多个0、1向量。

样本a的分布

多项式LWE

Ring-LWE

前置知识

Polynomial—LWE

  • Polynomial-LWE其实指的就是多项式LWE,但是要和上面的多项式LWE区分开来,上面的多项式LWE是用于帮助理解Ring-LWE所讲述的前置知识。
  • 而Ploynomial-LWE其实指的是多项式商环定义的LWE变体。

Module-LWE

LWE与格的关系

LWE与格问题的归约

LWE攻击

标准LWE攻击

R-LWE攻击

Search—LWE具体题型

LWE的搜索问题

MLWE的搜索问题

RLWE的搜索问题