矩阵分支程序的iO

Question

最近，我正在学习如何通过多线性映射从矩阵分支程序构造iO (确切地说，和)。然而，我有一个小问题，我搞不懂。

将程序/电路转换为模糊的程序/电路的步骤似乎是首先将程序/电路转换为MBP (一群M_{i,b}s)。然后，利用基利安随机化方法，加入随机2k R_i, R_i^{-1}矩阵，使MBP矩阵的分布呈现出随机性。接下来，我们将其应用到MMap框架中，该框架允许人们添加/乘加零测试。最后，有一些结构可以保护输入混合攻击。

我的问题是，为什么我们需要将这个MBP应用到MMap框架中？似乎在基利安随机化之后，MBP中的矩阵看起来是随机的，不会泄漏信息。我们就不能把随机的MBP作为程序的模糊版本发布吗？我觉得我漏掉了什么..。

Answer 1

问题是，两个长度相同的部分计算( \ell )将具有R_0 B_1 R_\ell^{-1}和R_0 B_2 R_\ell^{-1}形式。因此，由于攻击者可能知道B_1和B_2，所以他们可以了解一些混淆的分支程序。用多线性映射编码这些随机矩阵隐藏(或至少试图隐藏)这些关系。

考虑iO的安全定义。它说，攻击者选择两个等效的分支程序P_1和P_2，将它们发送给混淆器，然后接收模糊程序P。目的是猜测P是对应于P_1还是P_2。

现在，如果在没有多线性映射的情况下进行模糊处理，攻击者可以按以下方式破坏安全定义：

• 选择两个不同的矩阵A和B；
• 选择具有单个输入位的长度-2分支程序P_1，如下所示：\text{bit 0:} ~ ~ ~ ~ I ~ ~ ~ ~ A \text{bit 1:} ~ ~ ~ ~ I ~ ~ ~ ~ B \text{inp}(1) = \text{inp}(2) = 1
• 选择具有单个输入位的长度-2分支程序P_2，如下所示：\text{bit 0:} ~ ~ ~ ~ A ~ ~ ~ ~ I \text{bit 1:} ~ ~ ~ ~ B ~ ~ ~ ~ I \text{inp}(1) = \text{inp}(2) = 1

注意，P_1(0) = P_2(0) = A和P_1(1) = P_2(1) = B是等价的程序。

现在，如果P混淆了P_1，那么它就是\text{bit 0:} ~ ~ ~ ~ R_1 \cdot R_2^{-1} ~ ~ ~ ~ ~ ~ ~ ~ R_2 \cdot A \cdot R_3^{-1} \text{bit 1:} ~ ~ ~ ~ R_1 \cdot R_2^{-1} ~ ~ ~ ~ ~ ~ ~ ~ R_2 \cdot B \cdot R_3^{-1}的形式。

因此，我们可以通过检查第一步对应的矩阵是否相等来区分模糊程序。