2012年BIU密码学冬令营-03-Learning With Errors-第1部分

演讲视频简介

2012年BIU密码学冬令营Lecture 03的讲座如期而至。我们终于在Lecture 03遇到了格密码学之所以在近15年来蓬勃发展，最关键的安全假设：Learning With Errors（LWE）。Lecture 03主讲人Chirs Peikert是格密码学非常重要的研究人员。Lecture 03仍然分为两个部分，第1部分主要讲解LWE假设本身，第2部分讲解用Learning With Round（LWR）假设和LWE假设构建可证明安全伪随机函数（Pseudo-Random Function，PRF）的方法。

在整理字幕时，我也发现最开始版本中很多字幕都听译错误了，大部分原因是之前翻译时自己密码学的基础仍然很差（当然现在可能也很差）。密码学真是一门博大精深的科学啊…

演讲视频信息

演讲视频字幕

欢迎大家小休后再次回到讲座现场。在这次讲座中，我会讲解格中的另一个基础问题。这也是平均困难问题，我们经常利用这个困难问题构造密码学方案。这个困难问题叫做Learning With Errors。

Vadim已经讲解了Short Integer Solution问题，简称SIS问题，我们来回顾一下。这个问题要求找到个小的非平凡整数向量，使得 的和在模 下等于0。

为了方便起见，我们可以把这个问题写成这种紧致的形式，也就是用矩阵形式表述这个问题。即如果我们把 写成矩阵A的列向量，我们一共有m个列向量。我们还有一个m维向量z，我们把z乘到A的右边。我们希望模q后，相乘的结果等于0。

在这次讲座中，我将给大家讲解一个用SIS问题矩阵描述的互补困难问题。这个问题的表述形式和SIS问题非常像，但是性质完全不同，这就是Learning With Errors问题。但这个问题也有最糟糕情况困难性。

这就是Learning With Errors问题的当前发展状况。这一历程表明，人们如何逐渐明白这个问题为什么是困难问题。Oded在2005年提出了这个问题，他提出的是LWE问题的搜索版本。我们会在下一页幻灯片中讲到，LWE搜索问题在最糟糕情况下的困难度，至少不比解决SIVP问题和Gap Short Vector问题简单，所以从这方面讲 LWE问题和Vadim讲到的SIS问题非常像。唯一的区别在于证明困难性所构造的归约算法是一个量子算法。归约算法和Vadim讲过的算法非常像。你选一个高斯采样值，用一种很聪明的方法把这些值组合到一起。区别在于，你需要利用量子性质来把这些值组合到一起。这个归约算法用到了非常棒，是非常聪明的规约思想。

不过，这个思想的应用一定要借助量子计算机吗？2009年，我们证明，在特定情况下没有必要借助量子算法。第一个要说明的是，我们提出的算法不是把LWE问题归约到SIVP问题。迄今为止，我们只知道我们提出的算法只能归约到GapSVP问题上，不过GapSVP也是一个困难问题，所以我们给出的结论还是有意义的。第二个要说明的地方，我没有写在最新版本的幻灯片中。第二个要说明的地方是，我们的归约算法要求模数q非常大，q与n是指数关系，而不是与n成多项式关系。这就是第二个要说明的地方。这个说明不会录下来的，我这里不会讲这些结论的细节。不过如果你能等到周三的话，Oded会讲解这些结论的细节。他在前面的讲解中向大家承诺我会讲LWE问题，我现在遵守承诺。

在所有这些证明中，我不会为大家证明LWE搜索问题是困难的，具有最糟糕情况困难性。我要讲解的是规约过程右边的部分，证明LWE搜索问题不比LWE判定问题难，也就是说，如果LWE搜索问题是困难的，那么LWE判定问题也是困难的。这里也涉及到很多论文，各个论文在不同的条件和参数设置下证明了这个结论。最后，当人们设计密码学方案时，可以假设LWE判定问题是困难的，而LWE判定问题的困难性已经被这些论文所证明了。只需假设LWE判定问题是困难的，就相对可以比较容易地构造密码学方案。我这里会给大家讲解一些密码学方案的例子，这些例子都是基于LWE判定问题的。这就是LWE问题的概述了。

这张关系图起来比较简陋，因为我没法把所有的参考文献都列进来，这只是LWE问题历史层面的一个简单概述。这个图的柱状图以红色为背景，我很喜欢这张图，这是按照年份画出的柱状图。这个柱状图是我自己统计并画出来的，不具有科学性，带了点偏见性。这个图按年份显示了与LWE相关论文的发表数量，也就是证明LWE问题困难性的论文，或者LWE问题的新应用，亦或是有关LWE的新发现或者新的使用方法。2004年以前没有与LWE相关的论文，这个领域是2005年的一篇论文提出的。随后，密码学家花费了一段时间来消化这个困难问题。2008年发生了很有意思的事情，我们有3篇论文了。2009年我们有4篇论文。2010年我们有8篇论文。去年我们也有8篇论文。今年只有7篇论文，不过现在刚2012年2月。我们可以看到，论文数量呈指数级上升态势，知道能持续多长时间。而且，这还不是与格密码学相关的所有论文，只是与LWE相关的论文。LWE问题是一个重要的问题，LWE问题的潜力很大。

好了，引言部分到此为止，让我来给大家讲讲LWE问题是什么，这个很棒的困难问题是怎么一回事。有点像Vadim前面讲到的，我们这里也有一个n维空间，也有一个模数q。我们也有这些 。我们有这些向量 ，它们是 中均匀随机选取的向量。如果值是均匀随机选取的，在幻灯片上我都会用蓝色表示。我们有一系列 ， ，和前面讲到的SIS问题一样，但是我们还有一些其他参数。不光给定这些 ，我们还给出了 与秘密向量s的内积结果。你还有个秘密向量s，也在 中。LWE问题的要求是，给定这些内积，求得s的值。

我要强调一下，内积值都夹杂了随机噪声。如果没有夹杂噪声，如何解决这个问题？谢谢，如果没有噪声的话，很容易解决这个问题，用高斯消元法就能解决。高斯消元法太棒了，能用高斯消元法回答所有的问题。但在LWE问题中，这些等式中还引入了一些噪声。在理论上，你可以得到 ，任意多个 ，但这些都被某些噪声项扰乱了，你要在这种情况下解LWE问题。补充一下，内积都是在模q下计算的。这些是给定的参数，你可以获得无数个这样的等式来尝试求得秘密值s。有关噪声项，还要说明一下，这些噪声项是满足高斯分布的，这个要求可能没那么令人惊异。所以严格的说，所有这些χ，还有其他位置上的噪声，这些噪声都是从高斯分布采样得到的。

这里一个很关键的问题是，高斯噪声的方差取值应该是多少？我得花一些时间来讲一讲这些参数。LWE问题与一个叫噪声比例的参数相关联。噪声比例一般用α表示，我们可以把这个比例看成一个远远小于1的值，它约等于1除以一个n的多项式，这就是噪声比例。我们要做的是让噪声比例满足高斯分布，也就是让αq满足高斯分布。我们要在α上乘以一个q，使得噪声可以遍布整个 空间。因为技术原因，我们这里要保证αq要大于 ，我们后面会讲解原因。

本质上，αq是高斯分布的标准差，标准差至少要大于 ，也就是说，噪声的绝对值大致等于 或更大，而噪声的相对值要覆盖 。如果把噪声看成一个圆，α就是圆的半径，噪声相对值要覆盖 ，覆盖程度由α决定。如果噪声绝对值大于 ，噪声就可以保证隐藏 中不同的整数值了。这里大家有什么问题吗？这就是LWE问题了。再描述一遍，LWE问题的目的是找到一个秘密的s，前提是给定任意多个这样的等式。

LWE问题还有判定版本，目的是区分出通过这种方法产生的 对，所有 对都是按照这种方法产生的，要求从随机对中把这些对挑出来。这意味着，给定这些等式，他们或者是按照这种方式产生的，或者是完全随机产生的。你需要指出你得到的这些数对是按照这种方式产生的，还是完全随机产生的。这就是我们经常使用的LWE问题的两个变种。

我们可以把LWE问题写成矩阵形式，表述会更紧致一些。当然，你可能会我，在论文中好像一般不把LWE问题写成矩阵形式。这么写是为了把SIS问题和LWE问题联系起来，不过LWE中，我们把秘密向量乘在了矩阵左边。我们有一个矩阵A，列向量是 ，这与SIS问题一样，我这里要做的是在A的左边乘以一个s。本质上，我在A上进行行组合操作，得到行组合后，再加上一个噪声进行扰乱，噪声的每一个坐标都满足高斯分布。给定矩阵A，以及向量b，我需要求出秘密s的值，就是这里的s，或者指出a,b是不是按照这种形式生成的。

如果你年纪比较大，比如年纪比我大的话，你可能会知道一个困难问题，叫做Learning Parity with Noise问题。这个问题在1980年得到了些许关注，这是我能找到的最早的参考文献了，可能这个问题的提出时间要更早。密码学界对这个问题进行了一些研究，不过没研究多少。这几年，这个问题及其衍生问题有复苏的趋势。我想其中的原因是，人们已经意识到LWE是一个很重要的困难问题了。但是LWE问题是LPN问题的一般化形式，LPN问题中，模数是2，所以噪声变为了伯努利噪声。噪声只是1比特，噪声只是比特值，噪声基本上等于0，不过有不可忽略的概率等于1。LWE问题是这个问题的一般化形式。

现在我们遇到一个很关键的问题。正如Oded在第一个讲座中提到的，如何选取质数是一个很有趣的问题。如何选取这些参数，从而保证LWE问题是困难的呢？特别是，为什么我们对αq这个绝对值噪声参数有特别的要求？为什么αq至少要大于 ？这个问题可以这么回答，因为归约算法要求要满足αq至少大于 。归约算法很紧致，它告诉我们，为了让算法可以正确运行，必须满足上述条件，这也意味着围绕 这个参数，一定有一些有趣的结论。不过我们确实不知道 是不是一个最佳答案，可能当噪声更小的时候，LWE问题可能更难。不过现在已经证明， 是一个非常重要的门限值，因为Arora和Ge在去年发现，存在针对LWE的攻击算法，此算法的执行效率与αq平方呈指数关系。可能 后面还有个什么比例值，可能在某些地方应该要有，不过基本上等于 了，而且如果令αq远远小于 的话，LWE问题会遭到亚指数攻击算法的攻击。我们要避免LWE遭受这样的攻击，我们希望格问题是指数困难的，这就是我们相信这个参数是正确的原因所在。你可以证明，无论在LWE上增加何种噪声分布，只要噪声分布比较集中，就可以把噪声近似为高斯噪声，所以从某些方面讲，只要选对标准差，高斯噪声对于LWE来说已经足够了。所以，这也回答了为什么高斯噪声非常重要，以及为什么 是一个正确的门限值，大家有什么问题吗？我这里用一页幻灯片讲解了LWE问题，讲解了我们对于LWE问题知道些什么，以及有什么针对LWE的攻击算法。当然，这不是LWE的全部攻击算法，只是LWE非常重要的攻击算法。

这里我想给大家一个简单的对比，比较一下SIS问题和LWE问题。SIS问题的提出可以追溯到Ajtai在96、97年发表的论文，LWE是最近提出的，但他们在很多层面上都具有很高的相关性。不管是问题表述方式上，还是问题的意义上，都具有高度相关性。回想一下，在SIS中，我们有一个矩阵A，我们要求找到一个短向量z，当然要求是非零向量，使得Az=0。在LWE中，我们试着从完全随机值中区分带噪声的内积值。

这是我自己的结论和总结，如何从密码学假设的层次对比这两个困难问题。首先，从密码学层面上，可以把SIS看成是一个计算假设。SIS是一个搜索问题，这有点像整数分解问题，对吗？因为在整数分解中，给定你一个实例，你要去找这个实例的质因子。或者来对比下计算Diffie-Hellman问题，给定 ，你要试着计算得到 。SIS问题类似，要找到一个z来满足等式。但对于LWE问题，从密码学层面上我们可以把它看作为判定性问题。这有点像二次剩余问题，或者是DDH问题，也就是判定Diffie-Hellman问题。在判定Diffie-Hellman问题中，给定 以及另一个值，这个值或者是 ，或者是一个均匀随机值，本质是一样的。你要区分给定值满足一定条件，还是完全均匀随机的。

SIS问题有很多有效解，实际上有指数多个满足条件的z，你只需要找到一个就可以了。对于LWE问题，只存在唯一的一个解，只有一个满足条件的秘密值s。如果给定b，只存在一个秘密s，使得可以计算得到b。这种唯一性非常重要，我们正是利用这种唯一性来构造公钥密码学方案。这也是为什么我们可以基于LWE构造加密方案的原因。

另一个对比从某种程度上来说很有趣。LWE可以归约到SIS，也就是说，如果你可以解SIS问题，你也可以平凡解决LWE问题。假设我想解决LWE问题，但我拥有的是SIS预言机，某个人给我们一个(A,b)对，或者满足LWE形式，或者是完全均匀随机的，我可以做的是问询SIS预言机，得到SIS问题的一个解z。我可以得到一个很短的z，且Az=0。我可以做的是，计算b和z的点乘。如果b是LWE形式产生的，那当我在b的右边乘以z的话，你得到的是s乘以Az，而Az=0，所以所有这些都被消掉了，不存在了，剩下的是e乘以z。如果我们不往后看幻灯片的话，我们知道e乘以z满足什么性质？e是一个短的错误向量，对吗？e的坐标都很小，因为他们都服从高斯分布。而根据我们的假设，z也很小，z是SIS预言机给我们的结果，所以如果我们计算点乘的话，点乘结果也非常小。如果和q相比的话，点乘结果非常小。所以如果我们得到一个SIS解，然后我们计算点乘，如果b满足LWE形式的话，我会得到一个很小的值。如果b是均匀随机的，bz的结果就会很大，在整个空间中均匀随机分布。所以我们可以做的是，得到一个SIS解，计算点乘，然后看点乘结果比较大还是比较小，这就可以让我们区分A和红色的b，还是A和蓝色的b，这意味着LWE问题不比SIS问题难。你可能会问这个问题的反命题，是否SIS问题不比LWE问题难？这就没那么容易了。如果你有一个LWE预言机，你可以解决SIS问题吗？我们想一想这个问题，你应该能想到一些构造策略，但是这些想法都不太行，可能可以解决，不过我还没看到解决方法。但是从某种程度上说，这个命题应该是对的。如果我们可以使用量子计算机，SIS和LWE问题是等价的，这也是Oded要在周三给大家讲解的内容。我们这个讲座中讲解的内容不会涉及到量子计算机，但是使用量子计算机的话，确实可以证明，SIS问题和LWE问题是等价的。如果没有量子计算机的帮助，我们不知道如何回答这个问题，到现在为止还没有人能回答这个问题。这里大家有什么问题吗？

最后一个对比，Vadim在他的讲座中已经讲到了，SIS问题有很多很棒的应用。你可以得到单向函数、抗碰撞哈希函数、签名方案、ID方案。这些都被称为minicrypt，这些方案都可以通过单向函数来构造。但我们不知道如何利用SIS构造公钥加密。使用LWE，我们开创了格密码学中的cryptomania世界。这是个什么世界呢？在这个世界中，我们可以构造公钥加密、不经意传输、以及其他一些神奇的方案。所以，为了开创加密的华丽新世界，我们需要用到LWE。

正如Vadim所说，你可以把SIS问题看作是格问题，因为矩阵A定义了一个格，一个随机格，也就是对于所有的z，满足Az=0的格点。这个格看起来像左图这样。我们要做的是在这个格中找一个短非零向量。你可以认为所有这些绿色的点都是SIS的一个有效解。在LWE中，我们也可以做类似的工作。我们可以定义一个格，这个格看起来没那么直观。但本质上，我们得到的是矩阵A的行组合，这也会给你一个格。本质上说，A或多或少有点像格的基，当然是模q下的格基。矩阵A给定了一个绿色点所对应的格，LWE问题给定的是某个点b，这个点和某一个随机格点很接近，距离非常近，所以左图的球比右图的球大得多。你可以看到，这个点b确实和一个格点非常接近，所以GGH加密方案实际上是LWE问题的一个实例。这两张图从不同视角给出了两个问题的相关性。

在剩下的时间中，我们主要讲解LWE。我们来热热身，看看我们能得到哪些LWE的简单性质。首先，我们来看看LWE的一些简单性质。如果我们有一个LWE问题实例，比如某个A和b。假定我们解决了这个LWE问题实例，我们找到了秘密s，如何检测找到的秘密s是否正确呢？如何判断结果是对的还是错的？我们应该怎么做？相乘然后相减。我计算b减去候选s'乘以a，然后检测一下。我们怎么检测呢？检测结果值是不是比较小，对吗？因为如果我们得到的s是正确的，那么计算结果得到的应该是小的噪声项。如果我们得到的s是错误的，也可以很容易进行验证。如果是错误的，那么计算得到的结果应该遍布整个空间。计算结果有可能很大，有可能很小，但是不会都很小。所以如果你有很多等式，你取一个LWE实例，然后进行计算，只有当你得到的秘密是对的，所有结果才都会比较小。当看到结果都很小的时候，你可以确定你的秘密值结果是正确的。很好，很容易。

我们可以做的第二个事情也很简单，我可以对秘密值进行平移。我们有一个LWE问题实例，里面包含一个秘密值s。我要做的是把秘密值s换为另一个秘密值。实际上，我想把秘密值从s换为s+t，其中t是我自己选的值。我们应该怎么做？这里我不知道s等于多少，所以我不能再创造另一个LWE实例，但是我希望利用存在的实例，把它转换为秘密值不同的另一个实例。加上t乘以a的内积，对吗？所以对于我得到的所有b，我取b加上t乘以a，整理一下等式，得到的结果等于(s+t)乘以a，这样错误项可以传递下去。

很好，也很简单，但这两个性质实际上给我们的LWE一个非常强大的功能，这个性质叫随机自归约性。这让我们可以放大解决LWE问题的成功概率。我的意思是，如果我们有一个算法可以解决LWE搜索问题，它有非常小的概率可以解决LWE搜索问题，比如对于所有随机等式，只有1%的概率可以解决LWE搜索问题，我们可以把成功概率放大，让我们有非常大的概率解决LWE搜索问题。具体方法是，利用平移技术来重随机化秘密，每次产生一个新的LWE问题实例。我可以重新产生秘密，用我的预言机解这个新实例，得到候选答案，然后检测。如果答案是对的，我就赢了。如果答案不对，我再重新产生秘密，用预言机解，检测，以此循环。这样我可以执行很多次算法，每次有1%的成功概率，最后得到正确结果的概率就会非常大。我就重复100次，得到正确的答案。从密码学角度，我们要留意攻击者成功的概率，要十分留意这个概率值。我们要看看这个概率是不是不可忽略的，如果是不可忽略的概率，就可以用这个方法放大成功概率，从而解决LWE问题。

LWE问题的另一个很棒的性质是，你可以有多个独立的秘密值。如果你有t个不同的秘密值，你可以把它们组合成一个问题，判定它们都是LWE实例，还是都是随机值。你可以区分这两种情况。这也是大家的作业，我这里给出了提示。

我现在想讲一个非常有趣、非常聪明的算法。我猜这个算法首先是由Blum、Furst、Kearns和Lipton提出的。Oded的贡献是，他把这个算法带到了密码学领域，跟我们走到了一起。

这个论文内容是有关错误学习和密码学关系的，Oded把这个关系进行了推广，这就是我们今天看到的形式了。这就是搜索/判定等价性。这个定理的内容是，如果你有一个预言机，可以解决LWE判定问题，你也可以构造一个算法，解决LWE搜索问题。假设我们有一个预言机，可以解决判定问题。正如我前面所说的，我们可以假定这个预言机有100%的概率解决判定问题。如果给定a和红色的b，这个预言机会回答No。如果是a和蓝色的b，它回答Yes。这个预言机能以100%的概率区分红色的b和蓝色的b。我们希望利用这个预言机解决LWE搜索问题。我们希望给定a和红色的b，来找到a和红色b下隐藏的秘密值s。

我们来这样运行算法。首先我要简化假设，这里的模数q与n是多项式关系。我们首先关注，如何找到秘密向量的第一个坐标值，也就是第一个坐标值 。我要说明的是，这个已经足够回答，第一个坐标是0还是非0。这样一个预言机可以可靠地告诉我们 等于0还是不等于0。为什么这对我们找到 确切值来说就足够了呢？我猜答案已经在幻灯片上了，因为我们可以平移秘密值。我们可以依次平移 ，使其取遍0到q-1的所有值，预言机会告诉我们平移结果是不是等于0，这样我们就知道 的真实值了。这里我们只利用了前面讲到的平移技术。如果我们可以对 进行平移，我们也可以对 平移，这样我们就能得到s的全部坐标。为什么这里q=poly(n)很重要呢？因为我们要对所有的值进行平移，所以我们需要平移的总次数是多项式级的，我们对问题进行了简化。

我们只需要一个检测器，它能告诉我们第一个坐标等于0还是不等于0，而LWE判定预言机就是这个检测器。所以我取一系列(a,b)对，其中隐含了一个秘密s。对于每一个实例，我从 中选择一个新鲜、随机的r，然后我扭曲一下(a,b)对，从a的第一个坐标中减去一个r。我把(a',b)输入到判定器里面，我对判定器问询，这个对是满足LWE结构的，还是均匀随机分布的？判定器会告诉我答案。这是一个100%正确的判定器，它会告诉我这是个LWE对，还是随机对。

我们来看看会发生什么。我们做了个很聪明的事情，我们把a变换为了a'，我们来看看发生了什么。如果我们把b取出来，当然，b和a'满足一定的关系，b等于s乘以a加上一个噪声，所以b就等于s乘以a'，后面会多出这么一项， 乘以r，也就是秘密值与 的内积结果，这是简单的代数运算。所以这里的b满足什么条件呢？我们回忆一下，我们试着取判定 等于0还是不等于0。如果s_1等于0，会发生什么？这个项就消失了，而剩下的仍然是个LWE实例，对吗？剩下的项仍然是LWE的形式，b等于s乘以a'加上噪声，此时判定器会接受这个输入。它会说，嗯，这是LWE实例。如果 不为0，且q是一个质数，那么我们得到的结果是，一个随机数乘以任意一个非零值，模一个质数后，结果还是随机的。所以对于a'来说，b是一个完全随机的值，所以(a',b)对是完全随机的，D会拒绝这个输入。它会说，不对，这两个都是均匀随机的实例。这样我们就可以检测 等于0还是不等于0了。这就是我们要做的事情，这个算法允许我们把s的所有坐标都恢复出来，你就赢了，可以宣布胜利了。

这个算法可以工作，有两个前提条件。q必须是多项式大的，且q必须是质数。但实际上这两个条件都不是必要的，有很多论文的工作是去除这两个前提条件，最终使得对于任意q来说，这个结论都成立。所以q不一定是质数，q可以是任意形式，这会涉及更多的技巧，不过基本技巧是一样的。这就是为什么搜索/判定问题是等价的，这是个非常令人惊讶的性质，其他假设不具备这样的性质。如判定Diffie-Hellman问题和计算Diffie-Hellman问题，这两个问题不满足搜索/判定问题等价性。

我们还有一个非常令人惊讶的结论，这个结论要追溯到LWE提出之前。这个思想来自Daniele Micciancio。在2009年，我们给出了另一个版本，使得这个思想可以用到LWE中，不过本质思想是一样的。前面我们讨论的这个秘密值是均匀随机选取的，秘密值s要满足均匀随机分布。但如果秘密值的分布满足错误分布概率，那么LWE问题仍然很难。如果秘密值的选取满足高斯分布，LWE问题依然是困难的。我们一般称这个形式是标准形式，是LWE的Hermite标准型，这就让LWE和格问题联系到了一起。不过标准型在这里并不是很重要，你可能经常会听到 ”LWE标准型“这样的名词。

直观上说，这个结论有点奇怪。一般来说，均匀随机秘密值的随机性，要比标准差比较小的高斯分布随机值的随机性好。所以这和直观上的感受不太一样，这两种秘密值的分布带来等价的困难性。不过还可以从另一角度直观考虑这个问题。如果你想找到一个秘密值s，你也可以先去找错误向量e，对吗？找到错误向量e后要怎么做？高斯消元，很好，这个回答是正确的。如果你能找到正确的错误向量e，你就可以把它减掉，这样我们就得到一个没有错误的等式了。你可以利用高斯消元求得秘密s。所以这没问题，找到e也能解LWE问题。而且事实上，e是由错误概率分布得来的，这意味着你或多或少需要去对短错误项进行搜索。我们可以把这个方法变得更正式一点，当然了，这只是一个直观结论。我们实际上通过一种方法，把求一个秘密的问题转成了求另一个秘密的问题，其中另一个秘密是由错误分布概率得来的。这里只涉及到简单的代数技巧，我们简单看看应该怎么做。

整个过程分为两个阶段。第一阶段，你需要从LWE分布中得到一系列样本值。这样你就得到了 和 ，你要做的是得到一系列采样值，使得 是可逆方阵。如果样本值组成的 是不可逆的，你只需要扔掉这些样本值，重新采样一遍，直到得到一个可逆矩阵。这个过程不会花费太长的时间。我们只需要得到一个 ，我要得到n个样本值，得到可逆方阵 。随后，通过计算得到与之相关的 ，我把这两个值存起来，自己留好。现在我准备将与秘密s相关的样本值，转换为与秘密e横相关的样本值。这样，错误值就变为了秘密值，转换的结果就使得错误值成为了与样本值相关的秘密值。我们这么进行操作。给定采样值(a,b)，这个值与秘密s相关。我们仅需要计算a'，其等于 的逆乘以a，这么计算的原因暂且不谈。我们再取b，在b上加上 乘以a'。这些转换步骤看起来比较难以理解，因为 是可逆矩阵，这么计算a'是可行的。我们也可以计算 和a'的点乘值。我们有 ，a'是我们刚刚计算得到的，我们把表达式展开，很多值就被消除了。最后我们得到b'等于 乘以a'加上e。这实际上就是一个LWE采样值，不过与之相关的秘密值变为了 ，而不再是s。转换过程比较神奇，大家回去后把推导过程写一遍，展开一下，就可以理解整个转换过程了。

我们一直在讲解LWE。找到LWE中相关的秘密值，也可以不找秘密值，而是进行判定。我们现在来看看LWE的应用方法。我们来讲一讲公钥加密方案。用LWE构造的公钥加密方案，从形式上讲非常简单，这可能是你见过的最简单的加密方案了。

在公钥加密中，我们有一个用户Alice。Alice要选择一个私钥s。A是一个矩阵，矩阵A的列向量是随机选取的。Alice可以选择A，Alice也可以让可信第三方协助她选择A，可以用真正随机的方法选取A，让老天爷来选。所以我把A放在一个云的符号里面，她可以从云中得到A。

这是A，这是s，Alice的私钥是s。在我告诉大家答案之前，大家想一想公钥应该是什么？没人回答？试试看嘛。sA加上噪声，对的，所以公钥等于sA加上噪声，也就是红色标注的b。这就是Alice的私钥和公钥了。看起来挺好，没问题。

现在，Bob要给Alice加密一个消息。他选择一个m维的二进制向量x。注意，这里Alice把s乘在了A的左边，Bob把x乘在了A的右边。Bob选择了一个随机的m维二进制向量，这本质上有点像子集和问题，A列向量的子集和问题。这实际上是Vadim讲解的哈希函数。这是个抗碰撞哈希函数，Bob只是选择了一个随机项，然后做个乘法计算，他就得到了一个向量u。到现在为止他还没用到Alice的私钥，他只用到了从云上取下来的A。他接下来应该怎么做呢？我们从上帝视角看看，他如何加密1比特信息，或者说他如何用上Alice的公钥？他计算b乘以x。他取得Alice的公钥，然后右乘x，他还要把消息比特嵌入到密文里面。我们假设Bob只需要给Alice发送1比特信息。他通过下述方法把这1比特信息嵌入到密文里面。他把这1比特信息乘以q/2。如果q/2不是偶数的话，就取离q/2最近的整数。这里的关键点是，他或者发送b乘以x，或者发送一个离b乘以x非常远的值。这两种情况分别表示他要传输的比特值是0还是1。

这就是加密算法了，很简单很清晰。这就是公钥，用这种方法计算得到。密文用这种方法计算得到。Alice如何解密呢？减去Su，对吗？这里的关键点是u和u'的关系是u'等于u乘以s，所以Alice要做的就是计算u'减s乘以u。如果把表达式展开，你就能明白Alice得到的结果是什么了。我们来展开一下，看看能得到什么。b乘以x等于sA乘以x加上e乘以x。s乘以A乘以x，根据上述等式，就等于s乘以u。所以s乘以u与b乘以x的结果很接近。这两个结果都很好，唯一的区别是，这里多了一项x乘以e。这一项很小，x很小，e很小，他们的点乘结果也很小，所以这部分很小。这部分或者近似等于0，或者近似等于q/2。这就Alice的解密过程，到此为止，这是她解密的全部过程。

当然，这个加密方案只能加密1比特，不太好，你肯定想发送多个比特的信息。如何解决这个问题？对每个比特分别加密，对吗？所以Alice可以取一系列s，计算得到一系列b。Bob可以用相同的x进行加密。这就是如何发送多个比特信息的方法。

我们花一点时间分析下这个方案的安全性，来看看为什么这是一个安全的密码学系统。我们假定存在一个攻击者，他可以窃听全部通信过程。一个用窃听手段攻击的被动攻击者，可以看到双方发送的全部信息。他可以看到Alice的公钥，也就是A和红色的b。他还可以看到u和红色的u'。这就是他能看到的全部信息。我们用两个步骤来证明安全性。第一个步骤是，注意到LWE是个困难问题，所以很难通过(A,b)区分b是红色的b还是蓝色的b。如果我们把公钥换成完全随机的值，攻击者从攻击角度很难察觉到这一置换结果。所以我们可以这么做，我们把b换成蓝色的。接下来我们做一个思想实验，如果Bob加密时，所用的公钥是完全随机的，会发生什么？如果A和b是真正均匀随机的，没有私钥参与其中，你就可以证明加密是一次一密。无论消息比特是什么，密文都是均匀随机的。如果你深入观察的话，你会发现这实际上是左剩余哈希引理的一个应用，不过这里我们可以只用它里面涉及到的统计特性。因此，如果你有一个这种形式的公钥，这个公钥是完全均匀随机的，和私钥无关。如果用这个公钥加密，消息比特就被完美隐藏了，这个消息比特从信息论角度完全被一次一密所隐藏。这就是为什么攻击者无法得知你发送的是0还是1。我这里简单证明了方案的语义安全性，大家有什么问题吗？从美国来的各位有什么问题吗？现在是美国时间上午9:30，你们的一天才刚刚开始。

好的，这就是Oded在2005年他的论文中给出的密码学系统。我们再来看看另一个加密系统。你可能会想，Oded这个加密系统为什么不够好，为什么后面比较好？这也是这个加密系统提出的原因。不过让我先给大家讲一讲LWE用于加密的另一种使用方法，这种使用方法对于理解下一个加密系统来说很重要。这个系统称作对偶密码学系统。我觉得这个名字起得还是挺生动的。我们要做的就是把Alice和Bob的角色换一下。我们让Alice做Bob要做的事情，再让Bob做Alice要做的事情，听起来还不错。场景是一样的，这里有一个矩阵A。Alice现在选择一个随机的比特串x。Alice现在把它选的数乘在A的右边，得到她的公钥。大家可以发现，如果x足够长的话，公钥是均匀随机的，所以她的公钥是均匀随机的。现在Bob做以前Alice要做的事情。他选择LWE的秘密错误值s，然后乘到A的左边。Alice乘在A的右边，Bob乘在A的左边，方法一样。Bob计算s乘以A加上某个错误值，Bob再计算s乘以u，其中u是Alice的公钥，加上某个错误值。同样地，再在上面加上比特值乘以q/2。这个加密方案很清晰，我们只是把两个人的角色完全对调了一下，Alice的解密过程和前面是一样的。

从攻击者的角度，所看到的情景有些不同。攻击者可以看到矩阵A和u，这些是Alice的公钥。密文是b和b'，各个参数的构造方法如图所示。我们能得到什么结论？我们应该如何证明方案的安全性？特别地，对于b和b'，我们能得到什么结论？这是大家的作业题，不过这个问题与SIS问题难度相同。这很像SIS问题，区别是我们没在找Ax=0，而是在找满足Ax=u的x，不过这本质上是同一个困难问题。仅观察公钥的话，很难找到公钥中隐藏的私钥值。实际上这是一个很重要的观察结论，很难找到方案对应的合法私钥。因此，现在的场景是攻击者可以看到公钥和密文。你看到的所有密文，其形式均为s乘以A加上噪声，s乘以u加上噪声，A和u是均匀随机的，所以b和b'实际上是LWE的右半部分。很好，没问题。那这里的这个比特值呢？我要说的是，我们可以把这个比特值忽略掉。你可以在不考虑这个比特值的情况下，把b和b'都换掉。你可以把这两个值都换成真正均匀随机的值，这样的话比特值就被隐藏掉了，就像是一次一密。这个证明方法和用DDH来证明ElGamal公钥加密方案安全性是一样，很简单。所以，攻击者无法区分这几项。最后的结果是，所有的数值都是均匀随机的，没有消息比特了。

好的，我们还剩下几分钟的时间，我这里就不对比两个方案了。我想给大家讲另一个方案。我们跳过方案对比部分，我们直接看方案的效率。我们试着从效率的角度对比一下两个方案。我们看最下面的两行。最下面两行的意思是，矩阵A是在云上的，A不属于任何人，全世界任何一个人都可以用这个A。A有n行、nlog(q)列，所以这是个很大的矩阵，接近于n维方阵，其中n的取值大约是几百，存储空间占得比较大。属于用户的公钥和密文，这两项分别是nlog(q)和n，或者反过来，取决于我们使用第一个方案、还是第二个方案。因为这两个方案的区别只是双方的角色对调了一下。比较烦人的是这个log(q)项，我的意思是，其实n的平方这项更比较烦人，不过我们只能优化能优化的地方。

我们能做些什么呢？这是另一个方案的例子。这个方案依赖于LWE的标准形式，其中秘密是从错误分布中选取的。我们可以用这个方案消除log(q)项。在云上我们有矩阵A，这个矩阵就是n乘n的。现在Alice和Bob所作的工作基本是完全对称的，他们要做的事情几乎完全一样。和前面不太一样，前面两个人使用矩阵的技巧不太一样。Alice从错误分布中取一个秘密值。这里的关键点是，秘密值服从错误分布。她生成的公钥为s乘以A加上某个错误值。再强调一遍，秘密值不是均匀随机选取的，而是服从错误分布。Bob也做同样的事情。他从错误分布中选择一个秘密r，乘到A的右边，加上某个噪声值。他们做同样的事情，分别得到b和u。接下来，Bob在Alice的u上进行同样的操作，加上某个噪声值，用这种方法隐藏消息比特。现在所有过程都很清晰，都不难，但是Alice计算b'减去s乘以b，然后发现结果近似等于消息比特乘以q/2。为了保证等式成立，s要比较小，所以如果这里用的是均匀随机值得话，方案就没办法工作了。正是由于它很小，我们才能正确解密，Alice可以恢复出消息值。

这就是方案的工作过程，我们来想一想这个方案的安全性。如果你观察攻击者能看到的值，就会发现证明过程略有不同。第一步，我们把公钥换成均匀随机值，所以我们把u取出来，把它变成蓝色的。我们用LWE假设来置换u，这里用的是LWE的标准形式，因为秘密值是从错误分布中选取的。我们完成了置换，让公钥看起来是均匀随机的。一旦我们把公钥换为均匀随机的，我们可以进行第二步了。同样因为LWE，我们可以把密文换成均匀随机的。当然，这里用的还是LWE标准形式。这样，所有数看起来都是均匀随机的了，消息比特被完美隐藏在密文中。

这个方法可以追溯到Alekhnovich在2003年发表的论文。Vadim和他的朋友们给出了另一个版本，使之适用于子集和。我们又发现这个方法也适用于LWE。所以这个方法提出的时候没得到什么关注，然后这个方法被移到了子集和，最后被移到了LWE上面。这是应用LWE进行加密的三种方法，性能有所区别。不过我们可以注意到，最后一个方法中没有log(q)项了，公钥部分和密文部分的长度都只有n，而不是nlog(q)。

好了，我们总结一下，因为时间差不多了。我们回到刚开始。我们讲了LWE，LWE适用于Cryptomania世界，可以用来构造公钥加密方案。下一个讲座中，我们将回到Minicrypt世界。我们要用LWE来构造Minicrypt世界中的一些工具，而且这个工具的构造过程很有趣，引发了一些思想和启迪。