【格密码学习笔记(二十一)】回顾LWE、RLWE、MLWE

这里，我们来总结一下，具有代数结构的一些格，本文需要一点点抽象代数的知识，实际上，本身的知识，在之前的文章当中都有讲解，不太熟悉的读者，可以看下之前的文章，或者去学习一下有关于抽象代数的相关知识。

知识回顾

这里，我们先来回顾一下Ajtai's的哈希函数的构造，然后，我们再来看，为什么我们需要引入后续的代数结构，这里主要参考regev的paper[3]。

Ajtai's Hash Construction

• 参数选择: n, m, q, d
• 密钥生成: 随机均匀的选择一个矩阵
• 哈希函数的构造

这个哈希函数的构造是十分容易的，并且只涉及到了模q的加法和乘法运算，这么做似乎看起来是非常的nice，但是呢，我们来简单的计算一下，这个算法的开销，这里，直接采用原始的Paper当中的参数来计算，我们令, 以及，然后，我们知道，矩阵的规模是,因此，我们一共有个元素，在当中，这里，我们假设，我们需要得到100比特的安全强度，这里，我们取，并且我们取，因此，我们这里需要存储大约500000比特的私钥，当然，这个我们对于矩阵可以采用PRNG来生成，但是运算的时候，我们依然需要再内存当中存下完整的矩阵，并且，我们需要次的运算，这个开销，显然是比较大的，因此，需要想想办法，来减少。

循环矩阵(circulant matrix)

首先，我们来看一下，循环矩阵的定义，假设是一个列向量，然后，我们可以通过这个来生成一个矩阵（注意，这里的符号，和上面的，不是一个）

这个式子，实际上，我们是循环了当中的元素，然后，我们可以通过矩阵记号来改写一下。首先，我们定义一个矩阵

然后，矩阵可以写成如下的形式

这么看起来，比较复杂，我们通过一个例子来看一下吧。

样例

这里，不妨令，那么我们可以得到

然后，这里我们有

然后，这里，我们来看第3个元素吧，随便，来一个例子，这里

那么，这么做，有什么好处呢，我们接着来往下看。

多项式环

观察上面的形式，然后，我们回顾一下，比较一下，我们之前讲过的多项式的形式

他们之间有着一定的相似性，那么这两种结构之间，很大概率是存在着某种关系的，接下来，就来看一下，这两个，是如何联系起来的，那么为什么我们要联系起来呢，因为，如果可以联系起来，计算多项式的乘法是存在加速的，我们采用NTT的方案，可以将乘法的复杂度变为，这里显然，是要比 矩阵的乘法快得多的。

注意到，一个非常nice的结论，我们发现，并且，注意到是两两不同的，因此呢，这里其实对于乘法运算可以构成一个群，当然要添加单位元进去也就是单位矩阵，而对于加法来说，他也构成了一个交换群，因此，这里我们就得到了一个非常amazing的结论，实际上这个循环矩阵，可以构成一个环，我们稍微详细的描述下，首先我们定义集合

这里，我们显然有加法和乘法的保持，也就是对于我们有

然后，我们考虑多项式环，这里，我们有

发现，和我们上面的非常的对应，因此这两个环实际上是同构的，也就是说，我们可以用多项式来代表这个矩阵的运算。

理想(Ideal)

然后，我们先来，稍微回顾一下，本节，我们来谈一下理想，我们考虑R是一个环(这里，为了简单，我们考虑交换环，否则的话，要考虑左右理想)，然后如果存在一个集合，这个集合满足如下的特征

1. 在中，加法运算封闭，也就是如果，那么有
2. 环当中的元素与集合中元素，相乘，结果在中，也就是对于我们有

基于的多项式环

回顾了上面的知识呢，我们来看一个新的环，这里，我们可以发现

同样的，我们可以得到对应的循环矩阵元素

读者，可以自行验证一下，这里，我们可以得到

那么，我们为什么要采取上面的多项式呢，之前的多项式，有什么问题呢，我们来思考一下这个问题，我们知道

同样的，我们先来看一下环上的SIS的定义。

R-SIS

给定一个环R, 一个魔数q, 以及一个整数，给定个独立的系数均匀分布的多项式采样，目标是找到个不全为0的使得

实际上，利用这个构造的哈希函数是非困难的，我们令

注意到, ，然后，我们来看下面这个引理[4]

对于任意的以及，在上，如果我们令，那么的概率是，其中a的系数满足随机均匀分布。

这里，简单的证明下吧，如果可以被x-1整除，那么我们有，显然有

因此，的概率，即为可以被x-1整除的概率，因此，我们它的概率是1/q。

那么出现这种情况的核心原因，就是因为是可以被因式分解的，但是，这个是不能被分解的，当是2的幂的时候，我们称这个多项式为分圆多项式。

看完了这个，我们来回顾一下LWE的相关知识，这里简单的回顾一下。

LWE及其代数变体

错误学习(Learning with Errors, LWE)问题是Regev[5], 在2005年提出的一个问题，这个问题有两个参数，以及，然后，需要一个错误分布，然后，他有两个变体，分别是搜索的LWE以及决策的LWE，通常情况下，我们更倾向于采用决策的版本作为密码学的源语，我们，先来简单回顾一下他们的定义。

LWE(Learning with Errors)

首先，我们给定一个秘密的向量满足分布，考虑第i次采样，我们在下随机均匀的选择向量以及一个错误，其中服从错误分布。计算

最终，输出一个元组，我们称这个操作为LWE在分布的一个样本。

对于，搜索问题而言，我们需要找到，在给定多项式级别的样本数量后，而对于决策问题而言，我们需要区分样本，以及在随机均匀分布下获取。

R-LWE(Ring Learning with Errors)

接下来，我们来看一下RLEW[6]，这个是为了加速LWE的方案，首先令是一个多项式环，其中他的维度是N，并且是一个不可约多项式。我们同样的，描述一下它的采样过程，首先s的系数是一个满足key分布()的多项式，然后，我们按照如下的规则进行采样，还是假设我们是第i次采样，首先选择一个系数满足随机均匀分布的多项式以及一个错误满足错误分布，然后计算

最终，同样输出一个元组作为一次采样的结果，同样的，搜索问题，我们需要找到s，而决策问题，我们同样取，区分来自于均匀分布，还是来自于错误。

M-LWE(Module Learning with Errors)

考虑一个模其中，这里其中是分圆多项式，同样的，我们这里的私钥服从分布，注意，这里和LWE一样，是一个向量，只不过，这里向量当中的元素是多项式，然后，我们依然考虑第i次采样，这里，我们在上随机均匀分布的采样以及满足错误分布的元素，注意，这里是一个多项式，然后，我们计算

最终，我们依然可以得到一个元组，对于搜索问题而言，我们需要找到，而对于决策问题，我们需要区分随机均匀分布的样本$left(mathbf{a}{mathbf{i}}^{prime}, b{i}^{prime}right) in R_{q}^{r} times R_{q}$以及满足错误分布的样本。

总结

本文，简单的描述了一下(原来是想要详细描述来着，但是吧，发现，这个越看东西越多，实在收不住，所以，还是，简单描述下吧，主要是我菜，有些东西啃起来太费劲)，具体在环或者模上的格是如何来的，由于本人的水平有限，因此，难免会出现理解错误的地方，也欢迎读者和我交流，正是因为，如果我们采用原始的LWE的话，达到相同的安全参数，我们需要存储的密钥以及运算次数，都是非常多的，而利用循环矩阵，我们可以把矩阵采用多项式来表示，从而采用NTT来优化乘法运算，使得效率得到了进一步提升，而在[10]中，Martin R. Albrecht and Amit Deo给出了RLWE到MLWE的一个规约，也就是d维度的模q的MLWE可以相当于的RLWE，这应该也是，最终NIST选取了MLWE的原因吧，我猜的，好了快乐的时光过得特别快，又到了说再见的时候了，咱们下次再聊。

参考资料

1. Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’05, page 84–93, New York, NY, USA, 2005. Association for Computing Machinery
2. Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and learning with errors over rings. In Henri Gilbert, editor, Advances in Cryptology – EUROCRYPT 2010, pages 1–23, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg.
3. Daniele Micciancio, Oded Regev. Lattice-based Cryptography. July 22, 2008, https://cims.nyu.edu/~regev/papers/pqc.pdf
4. https://people.csail.mit.edu/vinodv/6876-Fall2018/RingSISclass.pdf
5. https://perso.ens-lyon.fr/damien.stehle/downloads/LWE.pdf
6. https://eprint.iacr.org/2019/930.pdf
7. https://crypto.stackexchange.com/questions/84122/mlwe-and-rlwe-to-lwe-reductions-proof
8. https://perso.ens-lyon.fr/damien.stehle/downloads/MSIS.pdf
9. https://malb.io/discrete-subgroup/slides/2018-01-15-deo.pdf
10. https://pure.royalholloway.ac.uk/ws/portalfiles/portal/28610024/612.pdf
11. https://cims.nyu.edu/~regev/papers/pqc.pdf
12. https://eprint.iacr.org/2023/895.pdf