本文作者东泽，来自安比技术社区的小伙伴，目前就读于斯坦福大学，研究方向密码学。
Average Case Hardness（平均困难度）
Lattice问题最有趣的一点就在于困难度的论证。因为我们知道格中的一些问题是难的，比如说之前讨论的SVP、CVP、SIVP等等，所以基于这些问题构造的新的问题也是难的。反之，如果我们能够解决基于这些难题构造的新问题，那么我们也就可以解决这些难题本身。这一推理的过程，我们称之为reduction（规约）。
在讨论困难度的时候，最常见的一种方法就是讨论平均的困难度，即Average Case Hardness。举个最简单的例子，在讨论像RSA一样依靠Factorization难度的系统的时候，我们会依靠我们的模组难以被factor这一难点来构造系统。比如说一个Modular Squaring的函数：这个函数就是计算一个数字在模组中的平方，得到一个Quadratic Residue。这个函数也是Rabin的密码学系统的精髓，它的难度在于如果可以逆向计算，我们也可以成功的factor 。那么这个函数到底有多难计算呢？我们需要看这个函数实例对应的这个模组有多难被factor。因为它们之间的安全关系是一一对应的。Rabin给出的安全性证明为：在密码学定义上，只要大部分是难以被factor的，那么这个函数也是难以被invert的。理解这个定义很简单，假如我们随便拿到了一个的实例，那么我们能够逆向它的可能性就基于我们随便拿到一个可以factor它的可能性是相似的。这也就是说平均的看（在Average case上），只要我们大概率拿到的是难的，那么也是难的。
同理可得，我们可以用这样的方法来分析之前提到的Ajtai OWF（即SIS）。
我们的OWF 的构造其实和之前的Quadratic Residue的构造很相似，同时我们在之前也指出了想要逆向计算的话，我们等于是需要求解Lattice 中的SVP问题。所以的SVP难度与我们的OWF的安全性也是挂钩的。这也就是说，如果我们随机的抽取矩阵，并且给予它来构造OWF。只要保证大部分时候中的SVP是困难的，那么我们得到的就是单向（OWF）并且collision resistant的。Average Case Complexity（平均复杂度）
我们上面讨论的两个类似的问题，即Modular Squaring 和SIS OWF ，我们都可以把它们的难度规约到解决一些特殊问题的复杂度上。
比如在的例子中，如果难以factor，那么对应的算法复杂度也很高。但是什么样的数字难以被factor呢？Factoring问题的定义是这样的：给定一个数字，输出一组整数，并且满足。使用很简单的数学尝试，我们就能发现，其实factoring的难度，和这个数字的分布有很大的关系。如果就是一个均匀分布的随机数字（uniformly random），那么：道理很简单，每两个相邻的数字中就一定有一个偶数，所以如果我们均匀的抽取随机数的话，factoring问题有一半的概率都是极其简单的。为了避免这个问题，我们在挑选的分布的时候需要格外的小心。如果我们挑选，并且选取为随机的质数，那么在这个新的的分布下，我们相信factoring是困难的。所以说，整个factoring问题的平均复杂度，同时也是的平均困难度定义，完全取决于我们如何挑选的随机分布。如果是一个较好的分布，我们这个OWF从平均来看就是安全的，反之则不是。这种精心挑选随机分布的方法对于其实很有用，因为我们可以很直观的选出较好的随机分布出来（选择为随机大质数）。现在我们来看Ajtai OWF。我们知道，只要的SVP问题困难，我们的SIS构造的OWF就是安全的。那么如果我们均匀的随机生成矩阵，这个矩阵构成的格中的SVP问题到底难不难呢？换句话说，我们如何选择一个有利于我们SVP问题难度的随机分布？这些问题，至少在现在，是很难有很好的答案的。Worst Case Hardness（最坏情况困难度）
对于，如果我们继续用平均困难度的方法，其实是很难得到一个很好的结果的。这个时候，我们可以换成另外一种思考角度，把这个平均问题进一步的规约成最坏情况问题。
这个reduction的方法其实不是很好理解，但是我们可以先来看一个假设。我们之前的Ajtai OWF的定义方法，我们随机生成的就对应了这么两个Lattice，同理也就对应了最多两个不同的实例，这样的话我们只能依靠平均困难度的方法来讨论的安全性。现在我们做一个新的假设：假如我们可以随机选择一个，然后构成一个Lattice ，但是有一种新的方法可以把这个Lattice映射到任意的上去。这也就是说和的一一对应关系已经没有了，一个Lattice可以变换组成任意的的实例。就像上图所示，我们一个Lattice 可以对应多个OWF实例，甚至这个对应的关系也不是唯一的，是有重合的。在这种情况下，我们困难度的证明一下子就变了。假设在所有的中，大部分的实例（对应的SVP问题）都是难解的，但是如果我们有一个算法可以破解所有可能性中的一小部分实例（即图上的白色圆圈部分），那么我们就可以用这个算法来破解所有其他的实例中的SVP问题。原因也很简单，因为我们一个Lattice 可以任意对应任意的实例，所以就算是这个空间中”最难“破解的Lattice ，也可以被映射到可以被破解的这一小部分上，然后用已知的破解算法来破解出来。这种类型的困难度论证被称为最坏情况困难度论证。也就是说，只要在整个取值空间中只要有任何（any）一个实例可以被破解，那么整个取值空间都可以被破解。当年Ajtai提出SIS的时候，就做了这样的一个reduction，使用最坏情况困难度来证明SIS OWF的安全性。具体的出的结论是：只要有一部分（some）的Lattice 中是难以计算SIVP的，那么基于随机取值的定义的是单向并且collision resistant的。看到这里，我不禁有一点一头雾水。之前我们看到的SIS的构造都是从构成的Lattice 直接构造成固定的实例，明明只有一种映射（或者两种，第二种就是），怎么能够实现上面说到的可以映射到任意的实例的假设呢？
不要急，下面来研究一下如何实现这一假设。在之前的文章中讨论过可以把一个格的每一个点作为圆心，然后画一个圆（球体），并且让这个圆的半径逐渐变大。
当圆的半径等于这个Lattice的覆盖半径的时候，整个空间都会被覆盖住。当整个空间都被圆形覆盖住的时候，这个覆盖半径就是任意一个点可以距离格点最远的距离。现在我们假设这些圆当作一个以格点为中心的随机误差的分布。这个时候，在空间中的任意一个点都可以被拆分成如下的形式：这里的就是Lattice 中的一个格点，则是误差分布中的一个随机误差向量。如果我们现在随机的选择一个格点，再从误差分布中随机的选择一个误差向量，把它们相加起来的话，就可以近似地得到一个空间中的随机向量。我们观察可以发现，图上的圆的半径仅仅是覆盖半径，整个空间中有很多部分重合的地方。这个时候我们用这种方法生成的随机向量的分布其实并不是均匀的，而是会偏向这些重合的地方。这个时候，我们需要继续增加半径的大小，使得这个分布变得越来越近似于平均分布。当我们的误差分布半径达到如上所示的值的时候，如果我们只看这个格的基础空间（即Determinant组成的parallelpiped，或者的模组空间），我们可以把这个空间中的错误分布看作平均分布。
这个时候，我们已经把这个格足够的模糊化了。当我们得到一个模糊化之后的Lattice之后，就可以来完成Ajtai OWF的安全性论证了。
最后，我们来尝试使用最坏情况复杂度的规约来证明Ajtai OWF的安全性（即单向和collision resistant）。
上一步我们成功的得到了一个模糊化之后的Lattice ，现在我们来看看这个格是否满足我们刚刚看到的假设，即可以映射到任意的上。首先，我们可以用上面提到的方法，先随机的生成一个中的格点。然后我们从随机噪音分布中生成一个噪音向量，并且根据我们模糊化的结果，。我们把这两个随机的向量组合起来，变成我们的目标向量。根据模糊化的结果，我们知道的随机分布是近似平均分布的。因为我们是拼接了个类似的随机向量得到矩阵的，所以这个矩阵也可以被看作是随机分布的。得到了之后，我们使用这个矩阵来构造一个Ajtai OWF的实例。这个时候，因为从根本看不出来我们原本的Lattice是什么结构的，对于一个adversary来说，这个就是一个平均情况的，可能是任何Lattice形成的一个Ajtai OWF实例。这个时候，就算我们一开始使用的是空间中“最难的”一个Lattice生成的随机向量，因为adversary并不知道这一回事，所以他只会觉得他在求解一个平均难度的问题。听起来感觉有些烧脑，但是这就是最坏情况到平均情况的规约的精髓了！我们把一个最坏情况的Lattice“伪装”成了一个平均情况的实例。这个时候，如果adversary拥有一个算法可以破解一小部分的的化，那么它就有一定的几率可以破解我们创造的这个实例。如果adversary可以成功的破解这个实例的话，那么就代表我们找到了一个短向量并且满足：观察可以发现，等式的左侧我们可以得到一个格点，而右侧我们可以得到一个相对来说较短的向量（并不是格点）。因为向量长度的上限和向量是个短向量的原因，我们可以约束右侧的向量：虽然右侧的向量并不在格点上，但是我们发现这个向量相对来说还是比较短的。因为左侧的在格中的向量的值等于右侧的向量的值，这就代表说左侧的格点向量也是很短的。这样一来，我们就等于间接的解决了中的短向量了。回到我们一开始的定义，如果找到了短向量（近似SIVP）问题，那么我们就可以成功的破解SIS OWF。根据我们最坏情况困难度的规约，只要所有的随机格中有任何一部分（some）Lattice可以被破解，那么我们就可以破解任何平均情况的Lattice，找到它们的短向量。综上所述，因为我们知道SIVP是困难的问题，所以这些事情都不可能，所以SIS OWF也是安全的了。写到这里，其实多少还是对于这个reduction有点模糊，并不是完全的掌握。想了想还有一个比较好的理解方法：如果只依靠平均情况hardness的话，那么代表在大部分情况下都是安全的， 但是不排除有踩雷的情况（生成了比较差的弱实例）。这就等于说是我们有一块地，可以确保80%的地方都是安全的，但是剩下的20%说不定有地雷，有窟窿，但是我们不知道，说不定那天就踩到了，这是令人感到很不安心的。但是如果我们依靠最坏情况的hardness reduction的话，那么代表在的随机取值空间中，可以被破解的实例几乎没有（negligible），所以整体都是安全的。因为只要有任何一部分（non-negligible）的实例可以被破解，那么基本上整个都会随之被攻破。这就好比是告诉我们有一块地，可以确保几乎没有任何地雷和窟窿（比如，negligible）。
封面图来自unsplash，作者Max Gotts
