本文作者东泽，来自安比技术社区的小伙伴，目前就读于斯坦福大学，研究方向密码学。
上一期，我们一起看到了【GGH+13】中提出的Multilinear Jigsaw Puzzle大致上是什么个思路。通过多线性配对这一神奇的工具，我们可以在不知道具体内容的情况下，直接在encoding上“同态计算”多线性配对算法，最后得到一个在目标group 中的计算结果。这一工具搭配Barrington‘s Theorem中介绍的矩阵分叉程序（MBP），我们就可以计算未知的MBP程序了。
上图是我们上一期结束时所构成的对于的第一次尝试：。大致思路如下：
- 随后，我们把这个MBP程序的矩阵部分encode成多线性配对中的group element，得到。并且我们额外的计算在目标group中的单位矩阵的encoding 。
- 最后，我们输出这一系列生成的元素作为电路的混淆：。
如果我们要计算输入对应的输出的话，那么我们就选择对应的encoding，根据MBP的计算方法使用Multilinear Map的算法来进行矩阵相乘，最后得到在target group中计算结果的encoding。随后，我们在这个结果的encoding中减去的encoding，就可以使用来完成计算：在达到正确性（correctness）之后，接下来我们的目标是达到所要求的安全性。我们在上一期结束的时候，已经提到了我们现在的构造的最大问题：因为多线性配对encoding中并不包含randomness，每个encoding都和它的原文保持着紧紧的关联性。基于这个关联性的攻击显而易见。我们之前举过一个最简单的例子：P0,P1都是对于AND逻辑门的一个正确的MBP程序，唯一不同的是的最下面一排矩阵都是单位矩阵。因为在indistinguishability的security game当中，Adversary可以任意选择两个功能性完全相等的程序，所以他可以选择传给我们的Challenger（挑战者）。我们的Challenger会根据我们之前定义的步骤，随机选择一个程序，然后输出对应这个程序的8个多线性配对encoding。由于encoding和原文之间的对应关系，所以我们知道，如果原文相同，那么encoding也会相同，反之也是（大概率相同）。所以Adversary就可以直接看返回的encoding中对应MBP程序最下面一排矩阵的4个encoding是否相等，如果相等的话，就知道Challenger选择的是程序了。如果我们仔细的思考这个问题的本质，之所以Adversary可以就算不知道encoding对应的是什么原文的情况下，就可以一下子分辨我们的“混淆”程序对应的到底是哪个程序的原因其实很简单：我们整个encoding系统中没有任何随机性（randomness）的参与。我们知道，一个加密算法，之所以可以保证语义安全（semantic security，即密文的不可区分性）的原因很简单，因为在加密的时候，我们引进了随机的nonce，所以在Adversary的眼中，两个不同的消息的加密在概率分布上是基本一致的。举个最简单的例子来说， AES是一个非常好的对称加密单元，我们可以把它当作一个很安全的PRP（Pseudorandom Permutation，随机排列）来使用。但是光用AES来做加密，即AES-ECB模式，是极其不安全的。AES-ECB模式下的加密就是直接计算，这也就是说，如果我们分别加密了两个一样的消息，那么这两个密文会看起来一模一样。光是这个相似的关联性就是致命的。这就是为什么，我们在使用AES来加密的时候，要正确的使用带有随机nonce的CBC或者CTR模式。简单的来说，就是我们在输入或者输出前会再额外叠加一层随机的mask，用来给密文增加随机性。这样一来我们才可以实现semantic security。这个问题在我们的中也格为显著。如果我们把多线性配对中的encoding这么个算法当作一个黑盒的话，那其实就和AES-ECB差不多，只起到了一个不可逆的映射的功能，但是对于两个完全相同的矩阵来说，他们的encoding是一模一样的。要想解决这个问题，我们就要试图在我们现有的系统中加入randomness。如果我们想要在整个系统中加入随机性的话，我们最要注意的就是在整个过程中不能破坏原本的功能性/正确性。如果我们就像AES-CBC/CTR一样，直接在原文上XOR随机值的话，那么这些随机化之后的矩阵就会失去原本MBP程序的含义，矩阵相乘的结果也只会是一团乱码。那么有没有什么方法，可以即保证矩阵相乘的正确性，又可以让每个MBP程序的矩阵都变得随机化，不可区分呢？1988年的时候，计算机科学家Joe Kilian在【Kil88】中做了一件很有意思的事情：基于MBP程序的Two-party MPC。当时Kilian遇到的问题很简单，如果Alice和Bob想要一起计算一个电路，其中输入可以被拆分为（我们假设分别都是一个bit），其中为Alice的输入，而为Bob的输入。目标就是构造一个协议，可以让Bob在不知道Alice的输入是什么的情况下，计算出的值来。当时Kilian选择的计算框架，正是来自于Barrington‘s Theorem的MBP框架。在MBP框架中，我们知道对应一个bit的输入就会有若干个对应的矩阵，所以我们可以想到一个很简单的toy protocol：
- 首先，Alice生成一个功能性与电路相同的MBP程序，随后她根据自己的输入选择好对应的矩阵，随后把这些选择发送给Bob。
- 随后，Bob通过Oblivious Transfer（OT）协议，从Alice处得到属于自己输入的MBP矩阵。如果对于OT不熟悉的话，我们可以大致理解为一个安全的协议，可以让Alice不知道Bob的选择的情况下，使得Bob获得Alice选择的其中的一个消息，而看不到另一个没选择的消息。
- 最后，Bob把这些矩阵相乘起来，得到MBP程序的运算结果。
当然，细心的朋友们会发现，因为Alice发给Bob的对应了她的选择矩阵是公开的，所以Bob就可以直接通过观察Alice选择的MBP矩阵是什么，反推出Alice的输入，整个协议并没有实质上的意义。
然而，Kilian却找到了一个非常巧妙的方法，解决了这个问题。Kilian发现，Alice在生成了对矩阵的MBP程序之后，可以通过一系列巧妙的步骤来“随机化”这个MBP程序。Alice只需要再随机的sample 个的纯随机矩阵，并且找到他们的inverse 。因为矩阵是随机的，所以大概率上是full rank的，反矩阵存在。获得了对随机矩阵及其inverse之后，Alice就可以把这些矩阵“叠加”到这对MBP程序矩阵当中，得到随机化的矩阵：其中，第一组和最后一组矩阵，即略微不同，只需要在一边乘上矩阵：我们很容易就会发现，通过这种方法叠加之后得到的新的矩阵仍然保持着MBP程序原有的功能性。如果我们把个随机MBP矩阵相乘之后，那么每两个矩阵之间的项就会直接相互抵消，最后仍然会得到我们想要的结果：
实现了功能性之后，我们再来看一下indistinguishability的要求。通过叠加了矩阵之后，原本的MBP矩阵其实就被彻底隐藏起来了。因为这个都是随机的，所以任何一组矩阵都不会相同，Bob也就没有办法通过看到Alice选择的随机矩阵来判断Alice的输入。Kilian在原文中甚至证明了：只要给定任何一个MBP的计算结果，我们可以完全的模拟（simulate）整个MBP程序中的每个随机矩阵！如果熟悉密码学的安全证明的话，我们就会知道，一旦我们能够证明simulation-based security，那一定就没啥问题了。simulation的要求比起indistinguishability要高得多。Kilian这里的这个随机化小技巧（Kilian Randomization）生成的随机分布的MBP，我们称之为Randomized Branching Program（RBP）。使用Kilian Randomization改进iOMBP
虽然说Kilian原本在【Kil88】中解决的问题是避免Bob通过Alice所选择的MBP矩阵推测出Alice的输入是什么，但是Kilian Randomization这个技巧同样适用于我们这里iOMBP的问题。
我们会发现，之所以我们描述的攻击是可行的，这是因为encoding没有randomness的成分， 而Kilian Randomization可以给我们的encoding赋予充分的随机性，避免这个问题。我们修改一下原本的设计，改进成随机化版本的。具体的步骤和之前非常相似，只是在生成MBP程序之后，我们要额外的sample 个随机矩阵并计算他们的inverse，随后根据【Kil88】的方法一样叠加到每个矩阵上。这样一来，Adversary看到的矩阵的encoding 也是随机分布的了。除此之外，Kilian Randomization还给了我们一个潜在的好处：不允许用户违背MBP程序的规则乱序的矩阵相乘。因为每一个矩阵都需要紧跟着下一个矩阵一起才可以把自己身上的randomness 给抵消掉，所以如果用户违反了这个顺序的话，最后得到的答案一定是一个乱码矩阵，无法从中提取出任何有价值的信息（计算结果）。看到这里，是不是已经有一种“拼图”的感觉了？我们可以想象着，原本是一盘散落的方块拼图（MBP矩阵），在经过Kilian Randomization之后，逐渐的每个方块上都出现了特有的棱角和花纹（RBP矩阵），并且我们只能按照某种规则把它们排列起来。只不过我们现在拼图上的花纹和棱角还不够明显，仍然可以被巧妙设计的攻击方法所击溃。回顾一下，我们现在的构造，所有的encodings 都已经加入了一定的randomness，所以直接相互比较的话，是无法从中获得任何与原本的矩阵有关的任何信息的。如果我们的Adversary只能够观察（observe）这些随机的矩阵encoding，而不能使用任何计算来进行交互的话，其实已经基本具备了不可区分的安全性！
然而，我们都知道，一个合格的Adversary，肯定不会这么简单的放弃。当我们无法从观察这些随机RBP矩阵中得到任何信息的时候，下一步自然而然的，就是通过违反RBP程序计算的规则来寻找漏洞。之前介绍MBP程序的计算方法的时候，我们都看到了其实我们需要遵守一套较为复杂的规则来得到最终的计算结果，尤其是这两条：
- 我们需要遵守这个mapping，正确的根据输入选择矩阵。
我们下面要介绍的两个潜在的attack分别对应上面这两条，这也是【GGH+13】一文中提到的，通过违反了RBP程序的计算规则而实现的attack。第二个问题：Partial Evaluation Attack（部分乘积攻击）
RBP程序虽然基于MBP程序的基础之上，加入了一系列的randomness 矩阵，但是这些随机矩阵的分布非常的有规律。
为了保证RBP程序最后的计算结果仍然有效，我们必须要把这些随机的矩阵和他们的inverse按顺序放在矩阵之间。同时，为了保证不管用户的输入是什么，最后都可以正确计算，我们必须要确保同一个下的都拥有一样的randomness：这也就是说，如果原本的矩阵都相等，那么加入randomness之后的也会是一样的！
基于这一点，我们可以构造出一个特别简单的attack。首先我们选择两个功能完全相等的MBP程序：其中的第一列对应第一位输入，第二列对应第二位输入，而的排列则是反过来的。整个程序的输出（或者）由第一位输入所决定。因为这个程序结构的特殊性，MBP矩阵中有一列都是矩阵，也就是不管对应的这位bit上的输入，我们选择的矩阵都是相同的。如果我们把这个程序转换成RBP矩阵（即加入randomness），我们会得到：我们会发现，在RBP的形式中，第二列上的两个随机矩阵也是相等的！这也就是说，如果我们输入的MBP矩阵在某一列（即对应某个）上的两个矩阵是相等的，那么在RBP中这一列上的矩阵也是相等的。在我们举的这个例子中，我们可以很轻易的通过判断混淆之后的RBP矩阵中，哪一列的两个矩阵的encoding相同，来判断混淆的到底是哪个MBP程序。这一类的攻击，被称之为Partial Evaluation Attack（部分乘积攻击）。一般来说这一类攻击中，Adversary只会计算RBP程序中选出的个矩阵中个矩阵之间的乘积（我们这里举的例子比较特殊，）。通俗的来说，Adversary会生成两组不同的输入，并且计算：因为这两条计算链（computation chain）中，不论的值是什么，每个位置上的矩阵所对应的randomness都是一模一样的，这也就是说，最后输出的结果并不会因为randomness存在而被混淆化。如果在原本的MBP中这两条计算链的输出是相同的，那么在RBP中也是相同的。基于这一点，我们就可以巧妙的选择不同的值来，通过观察结果是否相等，不仅可以区分RBP到底是“混淆”了原本的哪个MBP，甚至可以从RBP中提取出原本的MBP出来！Partial Evaluation Attack的本质
在我们试图修复我们的构造来抵御这一攻击之前，我们不妨来仔细观察一下，为什么Partial Evaluation Attack可以破坏我们构造的安全性。
我们会发现，Kilian Randomization可以确保在不同的位置上的矩阵之间的不可区分性，但是在相同的位置上对应0和1的两个矩阵仍然是相同的，并且我们使用不同的输入在evaluate整个RBP程序的任意一部分subset的时候，中间的randomness都被抵消，只剩下两侧完全相同的矩阵。这也就是说，之所以这一类的attack可以成功，代表整个系统中的randomness还不够！之前我们缺少randomness的时候，我们通过了Kilian Randomization的方法来加入一系列随机矩阵，在保持原本功能性的前提下，得到不可区分的RBP矩阵。现在看来，我们得想办法再引进一部分的randomness，以便避免Partial Evaluation Attack。在加入更多randomness之前，我们心里可能还会有一个疑问：既然整个RBP都是用多线性配对的框架包起来的，是不是只需要增强多线性配对的要求，就可以避免这一类的attack了？没错，由于我们这里的构造是双层构造，即一个可以计算的里框架（RBP），加上一个可以保证安全性的外框架（多线性配对），所以理论上我们可以在任何一个环节加入新的保护措施（safeguard），使得协议变得安全。但是一般来说，多线性配对的构造都比较脆弱，加入任何一点多的功能都可能会打破功能性和安全性之间的平衡，所以我们如果可以尽量增强里框架的安全性的话，就不要过多的依靠外框架的功能。综上所述，最好的选择还是使用常规（general）的多线性配对假设，改进我们的内框架，而不修改任何外框架的内容（把多线性配对当作黑盒来使用）。更多randomness：加入随机维度（High Dimensional Matrices）和挡板（Bookend）
有没有什么方法，可以既加入更多的randomness，使得就算在同一位上的矩阵也完全不相等，但是又不破坏RBP程序本来的功能性呢？
【GGH+13】中，作者把目光方向了扩展矩阵维度这一方案上。为了使得每个RBP的矩阵都足够随机，我们可以把原本的矩阵放入一个维度更大的矩阵当中。这个矩阵的维度为（稍后会说明是什么），并且原本的矩阵在矩阵的右下角。剩下的的左上角部分，我们就会在对角线上填充任意的中的随机值。注意这里的随机值是每个矩阵都会随机sample的，所以不会存在多个矩阵共享randomness的情况。同理，我们基于新的矩阵构造对应的RBP矩阵，注意这里我们用到的随机矩阵的维度也被放大到了。
为什么随机值要在对角线上填充呢？这是因为如果放在别的地方，在进行RBP程序运算的时候，随机值的部分可能会干扰到右下角的RBP矩阵相乘结果。当我们得到这一系列的矩阵之后，根据RBP程序的规则把它们按顺序相乘起来的话，那么最后RBP程序的结果就是右下角的的方格，而其他地方应该都是我们不需要关心的随机值。但是因为我们目前的计算结果是通过多线性配对的方式来获取的，而多线性配对只能做绝对的操作，并不能判断哪些是随机值。所以我们需要通过某些手段，把随机的部分去除掉。解决的方法很简单，我们在计算RBP程序，即做完矩阵相乘之后，我们额外的在两端加上一组挡板向量（Bookend vector）。这两个向量的长度均为。首先，向量的前个元素都为0，随后中间个为中sample的随机值，最后5个元素也是随机的，我们用来表示。向量构造也类似，只是前面个元素中，0元素的顺序换到了后面。
我们基于矩阵计算完RBP程序之后，我们可以额外的在最后的结果左右乘上与向量：
由于这两个向量的特殊构造，就像两个“挡板”一样，巧妙的挡住了我们刚刚加入的随机部分，我们最后就可以得到原来的计算结果了！这两个向量也因此得名，被称作为Bookend vector（挡板向量）。那么现在我们该如何使用多线性配对来验证计算结果呢？我们观察发现，如果RBP对应的计算结果是0，即最后的输出为单位矩阵，那么我们这里乘上Bookend之后得到的结果将会是：所以，我们只需要把最终计算的结果减去，就可以使用来判断RBP的计算结果是否为0了。此外，因为我们会把挡板向量作为混淆输出的一部分公开，所以我们同样需要使用Kilian Randomization的方法给他们叠加一些randomness，隐藏住它们的结构：![Image](data:image/svg+xml,<svg xmlns="http://www.w3.org/2000/svg" width="306" height="46"><rect fill-opacity="0"/></svg>)