本文作者东泽，来自安比技术社区的小伙伴，目前就读于斯坦福大学，研究方向密码学。
距离上一期介绍之后又过去了很长的时间。在这段时间里，笔者工作和学习略忙就没怎么来得及写新的文章。同时笔者也在疯狂的补习这一方面的paper，为了写的文章内容的正确性，纵览了上下十多年的学术研究。希望这篇文章能够对于想要学习了解的读者们带来一定的帮助！我们在上期回顾的历史的时候讲到过，自从Barak et. al.在【BGI+01】中提出了这个构想之后，一直到2013年，才由Garg et. al.在【GGH+13】中提出了第一个较为有信服力的构造（Candidate）。【GGH+13】的构造依赖于一种同样在2013年被刚刚提出的多线性配对（Multilinear Map）这一构造所带来的一系列特性。正因如此，很大一部分程度上，【GGH+13】的构造的安全性依赖于它所用的多线性配对的安全性上。我们在上期的时候也稍微提到过，现有的很多Multilinear Map的构造如【GGH13】、【CLT13】以及【GGH15】都存在一些潜在的漏洞，有的甚至已经被完全攻破了。好在，【GGH+13】仅仅是把多线性配对作为一个包装好的工具来直接使用，即只需要Multilinear Map对应的一系列算法的黑盒访问（Oracle Access），并不需要关心Multilinear Map具体的实现方法。这一点确保了，即使我们攻破了原有的Multilinear Map构造，我们也可以构造出新的替换上去，继续使得【GGH+13】保持原有的安全性。我们上期在最后也提到了，自从多线性配对的概念被提出了之后，整个学术界就进入了一系列的攻防战，戏称Break-and-Repair Cycle。这是因为之前提出的构造多多少少还是存在了一些小的安全问题，而这些问题就会被特定的Cryptanalysis（密码分析）攻击所指定，随后攻破多线性配对的安全性。这就是为什么现在学术圈更加倾向于假设更清晰、构造更简单的新一代的构造，如上期最后提到的今年得到突破性发展的【JLS20】以及【BDGM20】等等。虽说如此，笔者还是觉得一圈看下来，【GGH+13】的构造可以说是非常优雅、高效的设计。虽说它依靠了多线性配对这一非常不寻常（nontrivial）的构造假设，但是藏在整个构造背后的巧妙设计还是非常吸引人的。话不多说，我们这一期就来深刻的学习一波【GGH+13】的构造吧！P.S. 秉承深入浅出的概念，这一期我们只学习多线性配对的概念，但是并不讨论它的构造。因为【GGH+13】并不需要关心到它的具体结构，我们只需要知道如何调用多线性配对实现的目的即可。下一期我们再深入了解Multilinear Map中的【GGH15】构造。在我们进入长篇大论的讨论多线性配对以及具体构造的正文之前，我们不妨稍作休息，来重温一遍当年构造出【GGH+13】的这帮大佬们当时的研究思路。我们把时间退回到2013年初。这个时候，距离Gentry在【Gen09】提出FHE的可能性以及Bootstrapping的概念才过去了4年不到的时间。紧接着Gentry的发现，学术界投入了大量的经历开始研究更加高效实用的FHE构造。在这个领域比较有代表性的研究者有Brakerski，Vaikuntanathan，Gorbunov，Halevi，Sahai，Waters等等。当FHE的概念大红大火的时候，一部分的研究者们把目光聚集到了尘封了12年依旧的【BGI+01】对于Indistinguishability Obfuscation的畅想上。在此之前，大家都没有想出来要怎么构造这么一个可以“混淆”别的算法的这么一个机制。然而，当我们拥有FHE之后，这一切变得不一样了。FHE提出的概念，无疑就是我们可以在我们不知道内容的密文上同态的计算任何的函数，并且最后可以得到正确的运算结果（的密文形态）。光是这个概念，就非常的具有混淆的味道。很多人一下子就想到了一个idea：如果我们把想要混淆的电路的描述作为密文放入到FHE的密文中，然后基于FHE的密文我们可以同态计算内嵌了输入的Universal Circuit（全能电路）。全能电路这一概念我们在之前的文章中有所提到过，大致来说是一个万能的电路，其功能如下：我们输入一个电路的描述，与的输入，然后全能电路就可以计算这个输入的电路在上的值随后输出。为了方便同态计算，我们在这里把输入的值“嵌入”到当中，构成只有一个输入的全能电路。这样，我们在FHE加密的电路描述上计算，就可以得到这个电路的输出结果即了！
看起来我们距离已经非常接近了，但是现在拥有一个致命的问题：因为我们使用了同态运算，我们得到的的输出结果仍然是FHE的密文形态。这也就是说，如果没有一个FHE的密钥来解开密文，那么这个结果等于是没有任何用处的。同理，如果我们拥有了FHE的密钥，那么我们就可以很轻松的解开一开始用到的的密文，直接读取出被混淆的电路的描述！遇到这个瓶颈，问题就一下子变得很棘手了。和我们之前讨论【KW18】基于GSW的NIZK一文中提到的问题一样，我们无法直接公开FHE的密钥，这样任何人都能解开（类比于在【KW18】中，任何人都可以看到证明方的witness）。同时，我们也不能选用更弱的FHE，这样直接威胁到了密文的安全性。在【KW18】中，Kim于Wu成功的构造出了基于GSW的全同态承诺（FHC）然后通过一系列的indirection来使得NIZK的验证方可以正确的解开一个FHE的密文，而不影响其他FHE密文的安全性。在我们这里，问题变得更加严峻了：由于我们的应用场景是，所以我们只能一次性的生成输出混淆的电路，然后之后所有的内容就全部公开了。由于我们在混淆的时候并不知道混淆电路的使用者会选择什么样的输入，所以我们没有办法提前计算出可以让使用方解开他的密文的一次性解密密钥。
经过一系列无用的尝试之后，大家逐渐开始意识到：FHE的定义对于的应用来说，实在是太“严格“了。因为FHE归根结底是一个加密算法，所以它的一系列安全性，让我们无法选择性的向用户公开密文中的信息。所以就算用户可以成功的同态计算出的密文形式，我们也没有办法在保护FHE加密的安全性前提下让用户得知的具体答案。这个时候，大家就开始思索着，我们能不能找到一个类似FHE的这么一个工具，即可以让我们在不知道“密文”中包含的信息的情况下，“同态”的计算任意的函数，并且还提供一系列的接口让我们可以“提取出”密文中的一部分信息出来。而这个问题的答案，正是本次文章的主角：多线性配对。
Multilinear Map，即多线性配对，简单来说就是一个抽象的数学工具，可以让我们结合一系列的群元素（Group element），并且可以从结合的结果中提取出一部分的信息出来。假设我们现在拥有个循环群（Group），并且我们定义一个目标循环群。那么一个阶的多线性配对（Multilinear Map）对应一个算法：这也就是说，可以输入个对应了的群的元素，然后并且巧妙的把输入的元素的幂数相乘起来，最后叠加在输出的群中，得到作为结果。通过这样的构造，我们在不知道的值的情况下，通过这个多线性配对的算法，在个encoding即上计算就可以得到的乘积在group 中的encoding 。
同理，我们也可以在同一个group中对于两个group element 使用这个group内定义的group operation 得到与的和的encoding：如果大家跟着我们前文的思路看到现在的话，会发现这个概念和FHE中的同态运算非常的相似！这里的group operation 对应了同态运算中的加法运算，而多线性配对算法则对应了同态运算中的乘法运算。我们会发现：多线性配对所能支持的级数，代表了所对应的“同态计算”所能支持的乘法电路深度。如果我们构造了的多线性配对的话，给定，我们就可以计算最多三层以内的乘法和任何层数的加法如，但是我们不能计算出（因为包含了4层乘法）。然而我们在前文已经讨论过了，光拥有FHE的特性对于构造来说还不够，这是因为FHE的定义太过于严格了，计算结果是由密文形态存储的，所以我们不能简单的在不暴露密钥的情况下让用户得知计算结果。这里，多线性配对就完美的解决了这个问题：它提供了一系列的算法，使得我们可以提取出一部分关于密文的信息！
使得我们能够提取出密文信息的方法，恰巧就是多线性配对所拥有的另一个特性：零测试（ZeroTest）。一个Multilinear Map系统还定义了一个算法，这个算法输入一个目标group 中的元素，随后可以验证这个群元素是不是0在这个group中所对应的encoding：这也就是说，我们可以首先通过多线性配对算法把一系列encode了的群元素组合起来，得到它们的乘积所对应的encoding ，随后我们就可以使用算法来验证是否为0。这样我们只需要精心的设计使用多线性配对组合的电路，我们就可以通过这么一个零测试的算法来逐渐的推测出”密文“（即encoding）包含的具体信息。这就好比是原本的FHE是一个彻底的黑盒，信息放进去同态计算之后啥也看不到，除非把盒子打开。然而现在，使用多线性配对的话，我们就像是在盒子上打了一个小小的针孔。基于这个细微的零测试孔，我们就可以试图通过同态运算来变换内部的信息的状态，再透过这个小孔来提取出一部分的信息来！举个简单的例子，假如说我们用多线性配对encode了一个NP问题的witness 。那么我们就可以在上使用多线性配对来“同态计算”NP问题的验证电路。我们紧接着就会得到在目标group中的结果，我们就可以通过来判断证明是否通过：拥有了这么一个“超能力”之后，我们接下来的目的就是设计一系列的机制，使得密文在满足某些要求的时候会变成0，从而实现FHE所不能实现的功能。
虽然我们这次不会介绍多线性配对的具体构造方案，但是在接下来正式介绍【GGH+13】之前，我们来最后看一下多线性配对的最大问题：安全性。为什么要提安全性呢？这是因为我们可以很轻易的发现，由于上述我们描述的多线性配对的功能实在是太强大了，所以要真正安全的实现这么一个强大（但不能过于强大）的系统，非常的有挑战性。首先，我们整个构造的前提就在于多线性配对中的这些group encoding都是可以遮盖住原文本身的。这也就是说，如果我看到了代表的，我无法从中提取出的信息来。这一点在Diffie-Hellman协议中对应了离散对数假设。这一要求的原因显而易见：如果我们可以轻易的从encoding中提取出原文的信息，这就好比是FHE失去了加密的安全性一样，整个系统就会变得无意义。其次，一个多线性配对的构造要强制性的使得我们只能进行多线性配对操作。具体的意思就是，假如我们构造一个阶的多线性配对系统，那么任何一个Adversary都不能在这个系统的encoding上计算非多线性配对的操作。这些操作比如有超出阶的乘法，计算非线性函数等等。由于篇幅原因，我们在这里不多描述原因，但是往往对于多线性配对构造的攻击，会从找到这个构造中的一个非法操作开始逐步击破。最后，也是最重要的，就是多线性配对的构造除了之外不能过多的暴露关于encoding中信息。这就好比是如果我们只是打个小孔（允许零测试），那么我们就可以在一定的安全性保障下使用这个小孔来“提取”一部分信息，达到我们的计算目的。但是如果我们不小心打了个大孔，允许我们看到更多信息（比如说可以得知encoding的某一位），这一下子就会破坏整个构造的平衡。利用这个漏洞，Adversary说不定直接用它提取出所有的encoding来，那整个构造就失去意义了。我们在这里描述的，仅仅是构造多线性配对的一部分挑战。如果纵览近几年来对于多线性配对的Cryptanalysis攻击，我们会发现各种各样的进攻途径，都是瞄准了多线性配对系统在安全性与功能性之间巧妙的平衡性上来的。这也就是为什么即使【GGH+13】的算法提出之后，我们仍然并没有觉得我们彻底攻克了问题的难关。当然了，我们在这里不需要过于担心这一点问题！了解完Multilinear Map的大致构造之后，我们就终于可以开始这一期的正题了。
当我们假设拥有了多线性配对这一神奇的构造之后，我们之前提到的基于FHE的想法的一系列弱点便迎刃而解。
假设我们把需要被混淆的程序放在多线性配对的group encoding中，随后我们在encoding上“同态计算”Universal Circuit，随后我们就可以得到的计算结果（的encoding）了。然而，和之前不同的是，我们可以轻松的使用这一算法来得知是否等于0。如果我们进一步约束，电路是一个boolean circuit（即，输出只为1 bit 1/0），那么依靠这个我们就可以直接提取出计算的答案来了！我们知道，一个安全的多线性配对系统中，我们无法得知encoding的具体内容，所以自然的也无法分辨不同的电路的encoding的差别（对应了的不可区分性）。并且通过的方法，我们也可以验证得知一个boolean circuit的运算结果，我们自然可以把一个位输出的电路拆分成个1位输出的boolean circuit，然后用组多线性配对的系统来分别计算每一位的结果，再把他们拼接起来（对应了的功能性）。这样一来，整个构造就大功告成了。这就是基于Mutilinear Maps的的大概构造思路啦！接下来，我们就要顺着这个大方向摸清一条可行的路线，复现一遍【GGH+13】的构造～
我们在上一段中，已经大概的指明了一个大致的方向，但是在这个方向上，仍然有很多问题还没有解决：
带着这些问题，在2013年Garg-Gentry-Halevi-Raykova-Sahai-Waters提出了【GGH+13】的构造，正是秉承了我们上一段的思路，并且巧妙的解决了我们提出的这几个问题。【GGH+13】中所提出的构造，他们称之为Multilinear Jigsaw Puzzle（多线性拼图）。在他们的构造中，一个对于电路的混淆输出就是对多线性配对中的元素。用户可以根据自己的输入和一定的要求选择这个元素中的个元素，紧接着使用多线性配对的算法像把它们组合起来，最后再使用，就可以得到计算的答案。因为整体的计算过程就好比是用户在拼拼图一样（使用块拼图中的个拼出计算的结果），所以被形象的称为多线性拼图啦。
如上图所示，用户只需要根据规则选取对应的拼图块，拼接在一起计算多线性配对之后，就可以提取出的计算结果了。我们还可以注意到，这一些拼图块每一块都有自己特有的形状，这代表了我们只能选择组合一部分的拼图块在一起，只有拼接成一个符合要求的图案之后才能提取出有价值的计算结果来。这一特性恰恰就是【GGH+13】的精髓，确保了被混淆的电路可以安全的运行，并且不会暴露出任何其他信息出来。
聊完了Multilinear Jigsaw Puzzle（简称MJP）的大致概念之后，不禁会觉得这样的构造非常的生动形象，不得不佩服作者当时的想象与创造力。
其实呢，虽然【GGH+13】是第一个被提出的的 Candidate，MJP构造并不是凭空而来的。它的结构非常多的借鉴了前人留下的被研究了很多的计算框架。基于这些框架作者又发现了一系列的问题，并且找到了修补的方法。接下来，我们就跟随着作者的脚步一起，重新走一遍【GGH+13】的路。
我们之前已经提出了对于构造的大概想法，即：
- 使用某种方法把电路表达成多线性配对的encoding。
有了这个想法之后，很自然的我们就会产生一个问题：有没有一个已经存在的计算模型，可以很好的适配我们这里的需求呢？答案当然是肯定的。如果看过笔者的【全同态加密】系列的第四篇，即Bootstrapping的文章的话，我们其实在那里提到过一次。这个神奇的计算框架就是Matrix Branching Program（矩阵分叉程序），简称MBP。MBP和电路，多项式，图灵机一样，是表达计算（computation）的一种形式。假如说我们有一个由各种逻辑门组成的电路，并且它的深度（即逻辑门的层数）为，一共需要 bits的输入和1 bit的输出，即。如果想要计算这个电路在某个输入的情况下的输出到底是什么的话，我们就会把中的个bit一个一个拆开，依次放到电路第一层所对应的逻辑门的输入处，随后根据每个逻辑门的规则计算层，最后就能得到的输出啦。
同理，在MBP中，“计算”的概念有一些小的改变。同样的这个电路，我们如果用MBP表示的话，那么它就变成了组正方形二进制矩阵。其中的每一个，都对应了的位输入中的某一位（这个对应关系 是公开并且恒定的）。每一个值对应的都有两个矩阵，即。这两个矩阵分别对应了输入的这一位是0还是1。计算MBP的方式很简单：我们从0开始，依次选择，然后根据对应关系选取输入中的某一位。随后我们根据这一位的值（是0还是1）选择对应的矩阵。最后我们把选出来的个矩阵依次相乘，就可以得到MBP程序在输入上的计算结果啦：如何读取MBP的计算结果呢？如果最后我们相乘得到的输出为Identity Matrix（单位矩阵）的话，那就表示计算输出0，反之就是1。这也就是说，如果MBP程序和电路的功能相同，而的话，那就表示。我们拿上面的图举个例子。上图是AND门的MBP形态，其中1、3组矩阵对应AND的第一个输入，而2、4组矩阵对应了AND输入的第二个输入。假如说，那么如果要计算的话，我们就需要在1、3组选择对应的位置（即矩阵），而2、4组选择对应的位置（即）。最后，我们把这些选出来的矩阵依次相乘，就能得到运算结果了：我们发现结果得到了，这也就代表了啦。如果觉得好奇的话不妨代入其他的值进去试试～
MBP程序改变了我们对于传统意义上“计算”的认知，通过输入的值来选择不同的矩阵组合，并且把这些选出来的子集相乘（subset product）的方法，我们就可以得到计算结果了。
然而真正使得MBP发光发热的，在于1986年计算机科学家David Barrington提出的Barrington‘s Theorem。在【Bar86】中，Barrington指出，任何一个复杂度中，深度为的电路，都可以被转化成一个个二进制矩阵组成的Matrix Branching Program，并且。这代表了，如果电路的深度为
![Image](data:image/svg+xml,<svg xmlns="http://www.w3.org/2000/svg" width="306" height="46"><rect fill-opacity="0"/></svg>)