本文作者东泽，来自安比技术社区的小伙伴，目前就读于斯坦福大学，研究方向密码学。
讨论完了Ajtai OWF（SIS）的安全性之后，现在问题来了：因为SIS问题的定义需要一系列的参数，如何定义这些参数，才可以满足之前的安全性证明呢？
Ajtai在96年的paper中指出来，只要足够大（large enough），那么就是单向/collision resistant的。对于的值我们不去变它，因为这个决定了矩阵的维度。但是这个模组的大小，其实对于Ajtai OWF的安全性来说，差异是不会有太大的，所以大家的目光都放在如何尽可能的压缩的大小。在这篇paper中，Ajtai要求，才可以满足安全性证明。随后，在MR04这一篇paper中，Micciancio与Regev两个人进一步优化了这一证明，使得的情况下可以满足安全性。在GPV08中，Gentry，Peikert，Vaikuntanathan三个大佬又对证明做了一次优化，使得的情况下仍然安全。最后，在MP13中，Micciancio与Peikert把的大小压到了更小。在paper中，他们指出只要，那么Ajtai OWF就是安全的。原文中的定理是这样的：如果我们可以破解情况下的，那么我们就可以把这个破解算法当作一个blackbox，然后逐步破解更大的的Ajtai OWF，即模组为。接下来，我们可以看一下，如何通过反证法来保证的情况下，Ajtai OWF（即SIS）是安全的。
首先，为了让构造和证明变得简单，我们假设OWF 只接受二进制的短向量输入，即。然后我们假设我们拥有一个很强大的算法，可以轻易破解在固定参数的下的SIS问题。这个时候，我们就可以用这个算法作为一个黑盒（blackbox），来构造出一个新的算法，来破解模组下的SIS问题。首先，我们拿到一个想要解决的SIS实例。然后我们把它平均的横向切割成份。注意这个时候拿到的矩阵都是基于的模组的，我们需要想办法把它转化为模组的。实现的方法其实不难，我们只需要把每一个模组下的值拆分成就可以确保这些值都在的模组内了。具体来说，我们就可以把一个矩阵拆分成。这个时候，我们可以把个矩阵放到我们之前的黑盒中，得到并且满足：这样一来，我们可以把得到的个解和另外的矩阵结合起来，组成一个新的向量：我们把这些向量拼接在一起，组合成一个新的SIS问题矩阵：随后使用我们的黑盒，再次找到SIS问题的解，即满足。当我们得到了和之后，目标SIS问题的解就是这两个向量之间的tensor product，即：具体的正确性证明在这里就不多说了。不过意会到这一证明的精髓之后，我们会发现其实的大小可以被压缩到很小很小，但是再往下的lower bound就需要更复杂的证明过程。如果我们把压缩到最小，即二进制，那么这个情况下的LWE/SIS问题就被称作LPN问题（Learning Parity With Noise）。LPN问题也被认为是一个难题，但是现在似乎还没有很好的证明。接下来我们可以看一看SIS系统的运行效率。
- 第一部分是SIS的问题矩阵，大小由来决定。如果在Ajtai原版的假设中，。在这里，我们可以假设。
- 第二部分就是我们的OWF输入向量，如果在二进制短向量的假设下，那么输入的就是个bits。
我们观察发现实质上是一个把1024 bits的输入空间映射到512 bits的输出空间的一个压缩函数。（这里512由计算而来。）在OWF的使用场景中，矩阵则是我们OWF的key，这也就是说我们的key的大小就是。这对于一个小的OWF来说，key的大小有点太大了。同样，如果我们计算OWF的时候，矩阵相乘需要做次乘法，这也是非常巨大的一个数字。这就是为什么Lattice的诟病一直是效率低的原因。因为我们使用了一个二维的矩阵，所以我们做任何矩阵相乘运算的时候，复杂度一直都是的。那么有没有什么方法可以让我们低于这个复杂度，并且压缩密钥的大小呢？
如果之前存储与计算的瓶颈一直都在矩阵的大小上面，那么有没有办法消减矩阵的大小呢？
有一个很好的idea就是，如果我们并不全部随机生成整个矩阵，而是随机生成一部分，另一部分用一定的伪随机生成或者线性变换来生成，就可以大大的缩小密钥的大小了（不需要存储整个矩阵）。同时，如果根据短密钥延伸出来的大矩阵拥有某些数学特性，说不定我们也不需要通过矩阵相乘的办法来计算SIS OWF的输出。基于这个idea，可以构想出一个最简单的构造：我们就只需要随机生成中的一行（甚至更短），然后把这一行作为一个PRG的种子，随机的生成整个OWF的密钥。这样的话，我们的存储成本就变得很低，但是计算成本还是一样的，甚至会因为PRG的运算变得更差。这是因为PRG生成的数值都是近似随机的，没有任何数字之间的联系。所以我们对于一个随机生成的矩阵进行运算的话，只能通过矩阵相乘，即的方法来完成。第二个比较有意思的idea，就是我们可以随机生成一个向量，然后通过不停的旋转这一行向量的值，逐渐构成一个小的循环密钥矩阵：当我们生成这么一个循环密钥矩阵之后，我们如法炮制，一共生成个矩阵，然后把它们横向拼接在一起，形成我们的密钥矩阵：这个系统在M02（Micciancio）中被第一次提出，并且指出如果的维度选择合适的话，这样体系下的是单向的。这一系统的构造也和1998年提出的很有名的NTRU加密系统很相似。我们构造出的矩阵就是一堆小的循环矩阵拼接而成的，虽然这种形式下面构造的OWF的单向性可以被轻易证明，但是比较难的另一个安全属性是collision resistance。为了证明这一点，这个idea的核心思路就是：我们通过改变循环矩阵的生成方法，进而确保中的SVP问题很难解决，然后证明是collision resistant的。循环矩阵的Collision Resistance
首先，我们来看一看我们刚刚提出来的循环矩阵的构造，能否满足CR这一要求。举个例子，假设我们有上图这么一个循环矩阵结构下的SIS OWF的矩阵，并且给定了一组OWF的输入。我们能否找到这个输入的另一组collision，即找到另一个，使得呢？乍一看，这么大一个矩阵，似乎没有什么头绪。如果我们直接去找这个矩阵的inverse，那么也要花费很长的时间。正确的方法是利用SIS OWF的线性组合特性，即。如果我们要找到另一个collision的话，我们只需要求解这个矩阵的SIS问题的结果，即找到一个二进制短向量，使得。然后我们就可以轻松的通过组合这个SIS的解和原本的输入的方式，得到另一个collision：。这里为了保证二进制短向量的特性，我们相加两个向量之后需要做一些求模的处理。
找到这一条路之后，接下来的问题就是求解SIS问题了，即找到一个二进制短向量使得。我们可以观察一下，这4个小的旋转矩阵分别都是由四个独立的向量[1,4,3,8], [6,4,9,0], [2,6,4,5], [3,2,7,1]组成的。因为这些旋转操作都是有规律的，我们会发现其实循环矩阵中每一列的值加起来都是相同的。这也就是说，如果我们让乘以一个全是1的向量，我们就会得到四组参数相等的向量：
我们观察发现，如果我们全部乘以1的话，就可以得到这四个数字。现在的问题就变成了，我们能否找到一组以内的参数赋值，使得这些参数乘以这四个数字加起来最后可以等于0呢？这有点像是一个算24点问题了。很简单我们就可以找到：得到这个解向量之后，我们就可以在原本的输入的基础上加上或者减去这个解向量，就可以非常简单的计算出任意多种collision啦。
为什么上面构造的循环矩阵的SIS问题这么简单呢？这是因为我们可以对这个矩阵做进一步的分解，即观察到他们每一列加起来的值都相等这一特性，把问题简化。
为什么可以做这个简化呢？我们首先观察一下最左侧的循环矩阵：我们的初始生成向量为，这也就是说，这个向量的第一个元素1被分配在了矩阵的正对角线上，然后后面的元素依次分配在对角线周围。我们其实可以用一个旋转矩阵来表述这一变换的过程：如果我们反复叠加这一旋转矩阵，就可以从1的位置旋转到8的位置，然后再旋转到3的位置，等等。这样一来，我们可以用一组线性组合来表示：这其实就是基于旋转矩阵的一组阶的多项式！如果我们使用更加通用的表达方式的话，那就是：循环矩阵可以被表述成阶多项式的形式，并且这一结构与的多项式环是同构（isomorphic）的。这也就是说，我们可以使用一组最多为阶，每一项系数在以内的多项式来代替我们的循环矩阵。我们还注意到，当旋转的次数变得过多（超出了阶）之后，旋转到最下侧的数字会回到最上面来。这一点我们可以在这个多项式环中的乘法上定义：因为我们在的环中，比我们的环的大小要大1，所以说。当我们把用多项式表达之后，我们就会发现，这一多项式，其实是很好约分的：
这就是为什么我们可以非常简单的找到SIS的解，因为我们可以很简单的找到这个多项式环中的0交界点。因为我们发现循环矩阵可以很好的被多项式环代替，我们索性就把原本的SIS OWF的key矩阵变成个多项式拼接在一起。同理，我们把OWF的输入矩阵也变成个多项式：这样以来，我们就可以通过多项式相乘的方法来计算原本的循环矩阵版的SIS OWF了。随后得到的值也会是一样的，因为我们可以代入原本的旋转矩阵为这里多项式中的取值，然后等式全部成立。我们把这样的，通过多项式环中相乘（而不是矩阵相乘）的类似SIS问题，称之为RingSIS。RingSIS的好处是什么呢？首先，这和之前的循环矩阵的优势一样，我们只需要存储一组随机的向量（即多项式的参数赋值），就可以定义整个问题，这样的存储成本就很低。其次，多项式环中还有一个之前矩阵形式里不能实现的黑科技：多项式之间相乘可以通过FFT（快速傅立叶变换）来达到的效率。比起矩阵相乘的效率来说，是质一般的飞跃。
现在基于格的很多库都是基于多项式环来进行运算的，因为运算效率高，存储成本低。在RingSIS中，我们可以任意选择想要的多项式环。因为我们之前发现了这个环很好约分，所以对应的OWF容易被找到collision，所以我们可以考虑，换一个更加安全的环。为了通俗的表达各种多项式环，我们一般都把RingSIS问题中的环用来表示，其中就是任意一个monic polynomial。如果不能被进一步约分，那么我们就不能用同样的方法来更快速的找到collision。这样的话我们就可以把不能约分的多项式环下的RingSIS问题的难度规约到理想格（ideal lattice）中的SVP问题上来了。一个比较简单的例子就是。这个环和之前的环一样，也包括了所有的阶的多项式。唯一不一样的，是乘法的定义：在得到临界值的时候，因为我们的环的大小就是，比大1，所以我们可以用-1来表示。这样一来，和之前一样是一个Ring的结构，只是乘法的定义有所改变。根据多项式的特性，只要，即2的幂，这一多项式是不能被约分成更小的式子的。所以这种构造下的RingSIS，或者循环矩阵拼接成的SIS OWF，就是单向并且Collision Resistant的啦。封面图来自unsplash，作者Mehmet Turgut Kirkgoz
