参考资料：

1. Joe Kilian. Founding cryptography on oblivious transfer. In Janos Simon, editor, STOC, pages 20–31. ACM, 1988.
2. Barak B, Goldreich O, Impagliazzo R, et al. On the (im) possibility of obfuscating programs[C]//Advances in Cryptology—CRYPTO 2001: 21st Annual International Cryptology Conference, Santa Barbara, California, USA, August 19–23, 2001 Proceedings. Berlin, Heidelberg: Springer Berlin Heidelberg, 2001: 1-18.
3. Garg S, Gentry C, Halevi S. Candidate multilinear maps from ideal lattices[C]//Advances in Cryptology–EUROCRYPT 2013: 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26-30, 2013. Proceedings 32. Springer Berlin Heidelberg, 2013: 1-17.
4. Gentry C, Gorbunov S, Halevi S. Graph-induced multilinear maps from lattices[C]//Theory of Cryptography: 12th Theory of Cryptography Conference, TCC 2015, Warsaw, Poland, March 23-25, 2015, Proceedings, Part II 12. Springer Berlin Heidelberg, 2015: 498-527.
5. Garg S, Gentry C, Halevi S, et al. Candidate indistinguishability obfuscation and functional encryption for all circuits[J]. SIAM Journal on Computing, 2016, 45(3): 882-929.
6. Boneh D, Sahai A, Waters B. Functional encryption: Definitions and challenges[C]//Theory of Cryptography: 8th Theory of Cryptography Conference, TCC 2011, Providence, RI, USA, March 28-30, 2011. Proceedings 8. Springer Berlin Heidelberg, 2011: 253-273.
7. Jain A, Lin H, Sahai A. Indistinguishability obfuscation from well-founded assumptions[C]//Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. 2021: 60-73.
8. 什么是iO，基于多线性配对的iO：多线性拼图，从MBP开始构建多线性拼图
9. Computer Scientists Achieve ‘Crown Jewel’ of Cryptography

Indistinguishability Obfuscation

软件工程里的 Code Obfuscation（字符替换、加入冗余、汇编语言，使代码可读性差），严格意义上并不是好的混淆，因为人眼区分不出来的程序，并不意味着任意的 PPT 敌手（计算机程序）无法区分。事实上，使用反汇编工具，立即可以得到可读性不错的 C 代码。

密码学中的定义为：Virtual Black Box Obfuscation（虚拟黑盒混淆，VBB），一个 Obfuscator 将电路 $C$ 混淆为 $\mathcal{O}(C)$，就如同封装在了一个黑盒 Oracle 里，唯一可做的就是输入 $x$ 输出 $C(x)$，并且无法获得关于 $C$ 的其他信息。

当然，如果电路的输出本身就包含电路的信息（例如它打印自己的代码），那么混淆是无意义的，这种电路称为 Learnable Program。VBB 仅用于混淆 Unlearnable 的电路。但是 BGI+01 证明：存在一族 Unlearnable 的电路 C∗C^*C∗，那么任意的 Obfuscator 都无法混淆它的某个属性，但如果放入 Oracle 则可以隐藏这个属性。也就是说：通用 VBB 不存在（VBB Impossibility Result）。

BGI+01 提出了一种新的定义：Indistinguishability Obfuscation（不可区分混淆），一个 Indistinguishability Obfuscator 将两个相同功能的电路 C1,C2C_1,C_2C1​,C2​ 混淆为 iO(C1),iO(C2)i\\mathcal O(C_1),i\\mathcal O(C_2)iO(C1​),iO(C2​)，使得敌手无法区分这两个电路。

现在，我们给出不可区分混淆的正式定义：一个 uniform PPT 的机器 $i\mathcal{O}$ 称为关于电路簇 {Cλ}\\{\\mathcal C_\\lambda\\}{Cλ​} 的一个不可区分混淆器（indistinguishability obfuscator），如果它满足

1. 功能性保持（Functionality Preserving）：对于任意的 $\lambda \in \mathbb{N}$，任意电路 C∈CλC \\in \\mathcal C_\\lambdaC∈Cλ​，有
   Pr[C′(x)=C(x):C′←iO(λ,C)]=1Pr[C'(x)=C(x): C' \\leftarrow i\\mathcal O(\\lambda,C)]=1 Pr[C′(x)=C(x):C′←iO(λ,C)]=1

2. 不可区分性（Indistinguishability）：对于任意的 $\lambda \in \mathbb{N}$，任意的（non-uniform）PPT 区分器 $\mathcal{D}$，任意的一对电路 C0,C1∈CλC_0,C_1 \\in \\mathcal C_\\lambdaC0​,C1​∈Cλ​，如果 C0(x)=C1(x),∀xC_0(x)=C_1(x),\\forall xC0​(x)=C1​(x),∀x，那么
   ∣Pr[D(iO(λ,C0))=1]−Pr[D(iO(λ,C1))=1]∣≤negl(n)\\Big| Pr[\\mathcal D(i\\mathcal O(\\lambda,C_0))=1] - Pr[\\mathcal D(i\\mathcal O(\\lambda,C_1))=1]\\Big| \\le negl(n) ​Pr[D(iO(λ,C0​))=1]−Pr[D(iO(λ,C1​))=1]​≤negl(n)

3. 有效性（Efficiency）：混淆器是 PPT 的，其输出长度满足 $|i\mathcal{O}(\lambda ,C)|\le poly(|C|)$。因为任意函数都可表示为一个指数大的表格，它是不可区分的但是平凡的。

关于 NC1NC^1NC1 的不可区分混淆器：如果 Cλ\\mathcal C_\\lambdaCλ​ 是深度至多为 $O(\log \lambda )$ 大小至多为 $O(\lambda )$ 的电路簇。

关于 $P/poly$ 的不可区分混淆器：如果 Cλ\\mathcal C_\\lambdaCλ​ 是大小至多为 $O(\lambda )$ 的电路簇（带有多项式长度 advice 的多项式时间图灵机，非一致多项式时间）。

区分两个混淆：

• Obfuscation：程序混淆。保护生成方的电路信息，计算方可以在电路上多次执行任意的输入。
• Garbled Circuit：姚期智的混淆电路。一种基于对称原语的 2PC 方案，保护参与双方的输入，并不保护电路信息，且计算方只能执行某一组输入（通过 OT 协议）。

Multilinear Jigsaw Puzzles

在 GGH13 和 GGH15 中给出了基于格的多线性映射方案，而 GGH+13 基于此构造了多线性拼图，并给出了第一个不可区分混淆器 $i\mathcal{O}$ 的构造。但是后续人们发现了 GGH13 和 GGH15 的多线性映射的弱点，不过幸运的是 GGH+13 只将多线性映射作为一个黑盒来调用，并不关注它的具体实现。然而，多线性度 $n\ge 3$ 的多线性映射如何实现安全性是个问题；目前已知双线性映射是安全的。Lin 经过一系列研究，将多线性度降低到了常数级，最终在 JLS20 中成功将 iO 建立在了双线性映射上。

多线性拼图猜谜（Multilinear Jigsaw Puzzles）是多线性编码（multilinear encoding schemes）的严格子集，类似拼图一样编码值的组合受限。类似于双线性映射，素数 $p$ 阶群上的多线性映射（multilinear maps）为：
e:G1×G2×⋯×Gk→GT(g1x1,g2x2,⋯,gkxk)→gT∏ixi\\begin{aligned} e: G_1 \\times G_2 \\times \\cdots \\times G_k \\to G_T\\\\ (g_1^{x_1},g_2^{x_2},\\cdots,g_k^{x_k}) \\to g_T^{\\prod_i x_i} \\end{aligned} e:G1​×G2​×⋯×Gk​→GT​(g1x1​​,g2x2​​,⋯,gkxk​​)→gT∏i​xi​​​

易知 e(g1x1,g2x2,⋯,gkxk)⋅e(g1y1,g2y2,⋯,gkyk)=gT∏ixi+∏iyie(g_1^{x_1},g_2^{x_2},\\cdots,g_k^{x_k}) \\cdot e(g_1^{y_1},g_2^{y_2},\\cdots,g_k^{y_k}) = g_T^{\\prod_i x_i+\\prod_iy_i}e(g1x1​​,g2x2​​,⋯,gkxk​​)⋅e(g1y1​​,g2y2​​,⋯,gkyk​​)=gT∏i​xi​+∏i​yi​​，且 e(g1,g2,⋯,gk)=gTe(g_1,g_2,\\cdots,g_k)=g_Te(g1​,g2​,⋯,gk​)=gT​。有效的多线性型（valid multilinear form）就是任意的形如 ∏ie(xi1,⋯,xik)wi⋅∏jgTwj\\prod_i e(x_{i1},\\cdots,x_{ik})^{w_i} \\cdot \\prod_j g_T^{w_j}∏i​e(xi1​,⋯,xik​)wi​⋅∏j​gTwj​​ 的可通过群运算和多线性映射表示的任意组合。

多线性拼图猜谜，它是一个 PPT 算法组 $MJP=(JGen,JVer)$，

• 拼图生成器（Jigsaw Generator）：输入一些明文，输出拼图碎片（明文的编码值），这些拼图碎片只能以十分受限的方式通过群运算和多线性映射组合。

• 拼图验证器（Jigsaw Verifier）：输入拼图碎片以及一个关于这些拼图碎片组合方式的多线性型，验证这个多线性型是否成功地将碎片组合成了明文 $0$ 的编码值。

拼图区分符（Jigsaw Specifier）是一个三元组 {(kλ,lλ,Aλ)}λ∈Z+\\{(k_\\lambda,l_\\lambda,A_\\lambda)\\}_{\\lambda \\in \\mathbb Z^+}{(kλ​,lλ​,Aλ​)}λ∈Z+​，其中 k,l∈Z+k,l \\in \\mathbb Z^+k,l∈Z+，而 $A$ 是一个概率电路：输入素数 $p$，输出有序集合 {(S1,a1),…,(Sl,al)}\\{(S_1,a_1),\\dots,(S_l,a_l)\\}{(S1​,a1​),…,(Sl​,al​)}，其中 ai∈Zpa_i \\in \\mathbb Z_pai​∈Zp​ 是明文，Si⊆[k]S_i \\subseteq [k]Si​⊆[k] 是编码级别（encoding levels）。

多线性型（Multilinear Form）是一个四元组 $\mathcal{F}=(k,l,\Pi ,F)$，其中 k,l∈Z+k,l \\in \\mathbb Z^+k,l∈Z+，$\Pi$ 是有 $l$ 条 input wires 的多项式大小的电路，$F$ 是对电路 $\Pi$ 中每条 wires 的指标集 $S\subseteq [k]$ 的赋值。电路的构成和约束是：

• 一元减法门 $\ominus$，输入线和输出线的指标集相同，运算为 $(S,a)\to (S,-a)$
• 二元加法门 $\oplus$，输入线和输出线的指标集相同，运算为 (S,a1)×(S,a2)→(S,a1+a2)(S,a_1) \\times (S,a_2) \\to (S,a_1+a_2)(S,a1​)×(S,a2​)→(S,a1​+a2​)
• 二元乘法门 $\otimes$，输入线的指标集是 disjoint sets，输出线的指标集是不交并，运算为 (S1,a1)×(S2,a2)→(S1∪S2,a1⋅a2)(S_1,a_1)\\times(S_2,a_2) \\to (S_1 \\cup S_2,a_1 \\cdot a_2)(S1​,a1​)×(S2​,a2​)→(S1​∪S2​,a1​⋅a2​)
• 忽略门（ignore gate）$\square$，入度任意，出度为零
• 电路的 output wire，指标集是全集 $[k]$

多线性运算（multilinear evaluation）：输入为 X=(p,{(Si,ai)})←(k,l,A)X=(p,\\{(S_i,a_i)\\}) \\leftarrow (k,l,A)X=(p,{(Si​,ai​)})←(k,l,A)，且 $\mathcal{F}$ 的 input wires 的指标集赋值为 SiS_iSi​，如果在 Zp\\mathbb Z_pZp​ 上进行运算后，使得输出线为 $([k],0)$，我们说 $\mathcal{F}(X)$ 成功（在受限的组合下使得 $C(x)=0$）。

拼图生成器是一对 PPT 算法 $JGen=(InstGen,Encode)$，

1. 随机实例生成器 (p,prms,s)←InstGen(1λ,1k)(p,prms,s) \\leftarrow InstGen(1^\\lambda,1^k)(p,prms,s)←InstGen(1λ,1k)，输入为：安全参数 1λ1^\\lambda1λ 、多线性参数 $k$，输出为：素数 $p$、公开参数 $prms$、用于编码的秘密状态 $s$
2. 随机编码算法 $(S,u)\leftarrow Encode(p,prms,S,a)$，输入为：随机实例 $(p,prms,s)$、编码级别 $S\subseteq [k]$、明文 $a$，输出为：编码级别和 $a$ 的编码值 $u$
3. (p,X,puzzle)←JGen(1λ,(k,l,A))(p,X,puzzle) \\leftarrow JGen(1^\\lambda,(k,l,A))(p,X,puzzle)←JGen(1λ,(k,l,A))，给定安全参数 $\lambda$ 以及一个拼图区分符 $(k,l,A)$，先执行 $InstGen$ 获得随机实例 $(p,prms,s)$，然后执行 $A(p)$ 获得明文的有序集合 X:=(p,(S1,a1),⋯,(Sl,al))X:=(p,(S_1,a_1),\\cdots,(S_l,a_l))X:=(p,(S1​,a1​),⋯,(Sl​,al​))，最后使用秘密 $s$ 执行 $Encode$ 编码出一个谜题 puzzle:=(prms,(S1,u1),⋯,(Sl,ul))puzzle:=(prms,(S_1,u_1),\\cdots,(S_l,u_l))puzzle:=(prms,(S1​,u1​),⋯,(Sl​,ul​))。

拼图验证器是一个 PPT 算法 $JVer$，

1. $0/1\leftarrow JVer(puzzle,\mathcal{F})$，输入为：一个关于 $X$ 的谜题 $puzzle$、一个多线性型 $\mathcal{F}=(k,l,\Pi ,F)$
2. 正确性：如果满足 $\mathcal{F}(X)=([k],0)$，那么 $JVer$ 输出 $1$ 表示接受。如果满足 $\mathcal{F}(X)\ne ([k],0)$，那么 $JVer$ 输出 $0$ 表示拒绝。
3. 我们要求对于随机的 $JGen$ 输出，以极大概率 $JVer$ 对所有的多线性型都正确。

iO for NC1NC^1NC1

Randomized Branching Programs

根据 Barrington’s theorem，可以使用 5-PBP 分支程序 表达在 NC1NC^1NC1 中的布尔电路。GGH+13 在 Kilian 的多方安全计算的基础上，加入更多随机化技术得到了 NC1NC^1NC1 上的不可区分混淆。

Kilian 的两方安全计算：Alice 和 Bob 需要计算 $C(x,y)$，其中 $|x|+|y|=l$，令总的输入为 $\chi :=(x\Vert y)$，步骤如下，

1. 首先 Alice 将 $C$ 转化为 5-PBP 程序 {(inp(i),Ai,0,Ai,1)}i=1n\\{(inp(i),A_{i,0},A_{i,1})\\}_{i=1}^n{(inp(i),Ai,0​,Ai,1​)}i=1n​
2. 然后 Alice 选择 $n$ 个随机的可逆阵 {Ri}i=1n\\{R_i\\}_{i=1}^n{Ri​}i=1n​，计算 Aˉi,b=Ri−1Ai,bRi−1\\bar A_{i,b}=R_{i-1}A_{i,b}R_i^{-1}Aˉi,b​=Ri−1​Ai,b​Ri−1​，这里 $i-1(\mathrm{mod}n)$ 从而 R0Rn−1=IR_0R_n^{-1}=IR0​Rn−1​=I，我们将这个新的 5-PBP 叫做随机化分支程序（randomized branching program，RBP），Kalian 证明它可以完美隐藏（perfect hide）Alice 的输入 $x$ 与矩阵 Ai,χinp(i)A_{i,\\chi_{inp(i)}}Ai,χinp(i)​​ 之间的对应关系。
3. Alice 将自己的输入 $x$ 对应的矩阵 {Aˉi,χinp(i):inp(i)≤∣x∣}\\{\\bar A_{i,\\chi_{inp(i)}}:inp(i)\\le |x|\\}{Aˉi,χinp(i)​​:inp(i)≤∣x∣}，直接发送给 Bob
4. Bob 通过 OT 协议，获取到输入 $y$ 对应的矩阵 {Aˉi,χinp(i):inp(i)>∣x∣}\\{\\bar A_{i,\\chi_{inp(i)}}:inp(i) > |x|\\}{Aˉi,χinp(i)​​:inp(i)>∣x∣}
5. Bob 执行 5-PBP 程序 P=∏iAˉi,χinp(i)P=\\prod_i \\bar A_{i,\\chi_{inp(i)}}P=∏i​Aˉi,χinp(i)​​，根据 P=?IP\\overset{?}{=}IP=?I 判断计算结果 C(x,y)=?0C(x,y)\\overset{?}{=}0C(x,y)=?0

我们直接将上述协议中的 Alice 和 Bob 分别作为不可区分混淆的混淆器（obfuscator）和计算器（ evaluator），令 $C(\cdot ,\cdot )$ 是通用电路（universal circuit），Alice 的输入 $x$ 是待混淆电路的描述，Bob 输入 $y$ 输出 Cx(y)C_x(y)Cx​(y)。与 Kalian 协议不同的是 Alice 直接将 $y$ 对应位置的所有随机矩阵 {(Aˉi,0,Aˉi,1):inp(i)>∣x∣}\\{(\\bar A_{i,0},\\bar A_{i,1}):inp(i) > |x|\\}{(Aˉi,0​,Aˉi,1​):inp(i)>∣x∣} 都发送给 Bob，这使得 Bob 可以随意执行关于不同输入的多次计算。但是这将导致一些问题：

• Partial Evaluation Attacks：敌手可以针对不同输入 (x,y),(x,y′)(x,y),(x,y')(x,y),(x,y′) 计算部分矩阵乘 ∏i=jkAˉi,χinp(i)=Rj−1∏i=jkAi,χinp(i)Rk−1\\prod_{i=j}^k \\bar A_{i,\\chi_{inp(i)}} = R_{j-1}\\prod_{i=j}^k A_{i,\\chi_{inp(i)}} R_k^{-1}∏i=jk​Aˉi,χinp(i)​​=Rj−1​∏i=jk​Ai,χinp(i)​​Rk−1​，由于 Rj−1,RkR_{j-1},R_kRj−1​,Rk​ 是固定的，因此比较两者就可以获得内部的关于 $x$ 的矩阵 Ai,χinp(i)A_{i,\\chi_{inp(i)}}Ai,χinp(i)​​ 的信息。
• Mixed Input Attacks：由于每个 index 可能在 BP 中多次使用，如果敌手针对不同位置 $inp(j)=inp(k)=i$ 的矩阵选用不同的取值 yi=0y_i=0yi​=0 和 yi=1y_i=1yi​=1，这也会泄露 $x$ 的信息。
• Other attacks：敌手可能不遵守矩阵的代数结构，或者在矩阵上计算非线性函数。

下面，我们依次解决这三个问题。

Multilinear Jigsaw Puzzles

为了解决 Other attacks，GGH+13 使用多线性拼图，约束敌手无法执行非线性运算。

• 将 $JGen$ 作为混淆器，
  1. 首先执行 $InstGen$ 获得一个多线性度（multi-linearity）为 $n$ 的随机实例；
  2. 由 Jigsaw specifier 给出上一节中的 RBP 程序，它有 $n$ 对明文矩阵；
  3. 执行 $Encode$ 对矩阵进行编码，将 Aˉi,b\\bar A_{i,b}Aˉi,b​ 的每个 entry 以级别 {i}\\{i\\}{i} 编码（受多线性型的约束，每个矩阵至多在乘法链中出现一次）。
• 将 $JVer$ 作为计算器，受限地计算矩阵乘积，并验证结果是否是单位阵。

Bookends Components

为了解决 Partial Evaluation Attacks，GGH+13 认为关键在于随机性不够多，于是通过扩张矩阵维度来加入更多随机性。

对于 5-PBP 中的矩阵 Ai,bA_{i,b}Ai,b​，将它扩充到更高维，
Di,b=[$⋱$Ai,b],Dˉi,b=Ri−1Di,bRi−1D_{i,b} = \\begin{bmatrix} \\$\\\\ &\\ddots\\\\ &&\\$\\\\ &&& A_{i,b} \\end{bmatrix}, \\bar D_{i,b} = R_{i-1} D_{i,b} R_i^{-1} Di,b​=​$​⋱​$​Ai,b​​​,Dˉi,b​=Ri−1​Di,b​Ri−1​

其中 $$$ 表示随机数，Di,bD_{i,b}Di,b​ 是 $2m+5$ 阶矩阵，它的左上角是 $2m$ 阶随机对角阵，这个对角阵关于每个 Ai,bA_{i,b}Ai,b​ 是唯一的（不要复用）。随机化矩阵 RiR_iRi​ 的维度也提升到了 $2m+5$ 阶。

虽然没有理由认为 $m=1$ 不安全，GGH+13 还是选取了较大的 $m=2n+5$ 以抵御非预期的攻击。

现在，RBP 的计算结果为 ∏iDˉi,χinp(i)=R0PRn−1\\prod_i \\bar D_{i,\\chi_{inp(i)}} = R_0PR_n^{-1}∏i​Dˉi,χinp(i)​​=R0​PRn−1​，其中 P=∏iDi,χinp(i)P = \\prod_i D_{i,\\chi_{inp(i)}}P=∏i​Di,χinp(i)​​ 的右下角的 $5$ 阶子矩阵为原始 5-PBP 的计算结果 A=∏iAi,χinp(i)A=\\prod_i A_{i,\\chi_{inp(i)}}A=∏i​Ai,χinp(i)​​。为了提取它，GGH+13 设计了特殊的”书挡向量“（bookend），它们被分为 $m+m+5$ 三块，
s=(0,⋯,0,$,⋯,$,−s∗−),t=($,⋯,$,0,⋯,0,−t∗−)s=(0,\\cdots,0,\\$,\\cdots,\\$,-s^*-),\\ \\ t=(\\$,\\cdots,\\$,0,\\cdots,0,-t^*-) s=(0,⋯,0,$,⋯,$,−s∗−),  t=($,⋯,$,0,⋯,0,−t∗−)

将 sˉ=sR0−1\\bar s=sR_0^{-1}sˉ=sR0−1​ 以及 tˉ=RntT\\bar t=R_nt^Ttˉ=Rn​tT 作为 RBP 的一部分。容易看出 r:=sˉ⋅∏iDˉi,χinp(i)⋅tˉ=s∗At∗Tr:=\\bar s \\cdot \\prod_i \\bar D_{i,\\chi_{inp(i)}} \\cdot \\bar t = s^* A {t^*}^Tr:=sˉ⋅∏i​Dˉi,χinp(i)​​⋅tˉ=s∗At∗T，当 $A=I$ 时它为内积 r∗:=⟨s∗,t∗⟩r^*:=\\lang s^*,t^* \\rangr∗:=⟨s∗,t∗⟩，当 $A$ 是随机置换阵等于这个值的概率约为 $1/p$。

因此，判断 Cx(y)=0C_x(y)=0Cx​(y)=0 就是用 $JVer$ 判断 r′:=r−r∗r':=r-r^*r′:=r−r∗ 是否为零，除了一个较小的错误率。

Multiplicative Bundling

为了解决 Mixed Input Attacks，可以类似 SPDZ 或者 ZKsnark，通过“牺牲”另一个相同的程序，来确保敌手的计算步骤的合法性。

GGH+13 使用乘法捆绑（multiplicative bundling），随机选择 {αi,b}\\{\\alpha_{i,b}\\}{αi,b​} 构造计算 Cx(y)C_x(y)Cx​(y) 的主程序 (s,t,{Di,b′})(s,t,\\{D_{i,b}'\\})(s,t,{Di,b′​})，
Di,b=[$⋱$αi,bAi,b],Dˉi,b′=Ri−1Di,bRi−1D_{i,b} = \\begin{bmatrix} \\$\\\\ &\\ddots\\\\ &&\\$\\\\ &&& \\alpha_{i,b}A_{i,b} \\end{bmatrix}, \\bar D_{i,b}' = R_{i-1} D_{i,b} R_i^{-1} Di,b​=​$​⋱​$​αi,b​Ai,b​​​,Dˉi,b′​=Ri−1​Di,b​Ri−1​

然后随机选择 {αi,b′}\\{\\alpha_{i,b}'\\}{αi,b′​} 构造计算 $f(x,y)=1$ 的虚拟程序 (s′,t′,{Di,b′})(s',t',\\{D_{i,b}'\\})(s′,t′,{Di,b′​})，
Di,b′=[$⋱$αi,b′I],Dˉi,b′=Ri−1′Di,b′Ri′−1D_{i,b}' = \\begin{bmatrix} \\$\\\\ &\\ddots\\\\ &&\\$\\\\ &&& \\alpha_{i,b}'I \\end{bmatrix}, \\bar D_{i,b}' = R_{i-1}' D_{i,b}' {R_i'}^{-1} Di,b′​=​$​⋱​$​αi,b′​I​​,Dˉi,b′​=Ri−1′​Di,b′​Ri′​−1

为了保证当 $A=I$ 时，主程序的结果 r:=s∗At∗T⋅∏iαi,χinp(i)r:=s^*A{t^*}^T \\cdot \\prod_i \\alpha_{i,\\chi_{inp(i)}}r:=s∗At∗T⋅∏i​αi,χinp(i)​​ 与虚拟程序的结果 r∗:=s∗′It∗′T⋅∏iαi,χinp(i)′r^*:=s^{*'}I{t^{*'}}^T \\cdot \\prod_i \\alpha'_{i,\\chi_{inp(i)}}r∗:=s∗′It∗′T⋅∏i​αi,χinp(i)​′​ 相同，这需要满足两个约束条件：首先是 ⟨s∗,t∗⟩=⟨s∗′,t∗′⟩\\lang s^*,t^* \\rang = \\lang s^{*'},t^{*'} \\rang⟨s∗,t∗⟩=⟨s∗′,t∗′⟩，其次是
∏inp(i)=jαi,b=∏inp(i)=jαi,b′,∀j∈[l],b∈{0,1}\\prod_{inp(i)=j}\\alpha_{i,b} = \\prod_{inp(i)=j}\\alpha_{i,b}',\\forall j \\in [l],b \\in \\{0,1\\} inp(i)=j∏​αi,b​=inp(i)=j∏​αi,b′​,∀j∈[l],b∈{0,1}

如果敌手遵循了 PBP 的计算法则，那么 r′:=r−r∗=0r':=r-r^*=0r′:=r−r∗=0 就正确反映了 Cx(y)=0C_x(y)=0Cx​(y)=0 的计算结果。而如果敌手试图采取 mix-and-match 的攻击，那么主程序和虚拟程序的结果将是独立随机的，只有 $1/p$ 的概率使得 r′=0r'=0r′=0

iO Candidate for NC1NC^1NC1

方便起见，我们定义 Ij={i:inp(i)=j}I_j=\\{i:inp(i)=j\\}Ij​={i:inp(i)=j}。另外，我们将 $inp(\cdot )$ 扩展到集合上，定义 inp(S)={inp(i):i∈S}inp(S)=\\{inp(i):i \\in S\\}inp(S)={inp(i):i∈S}，以及 IJ={Ij:j∈J}I_J=\\{I_j:j \\in J\\}IJ​={Ij​:j∈J}。

综合上述的技术，我们获得了如下的安全性更好的 RBP 程序：

我们使用多线性拼图来执行上述的长度为 $n$ 的 RBP 程序：首先执行 $JGen.InstGen$ 获得多线性度为 $n+2$ 的随机实例，然后执行拼图区分符 $(k,l,A)$ 获得上述的 RNDp(BP)RND_p(BP)RNDp​(BP) 及其编码索引，接着执行 $JGen.Encode$ 将它编码为

给定一组输入 χ:=(x∥y)∈{0,1}l\\chi:=(x\\|y) \\in \\{0,1\\}^lχ:=(x∥y)∈{0,1}l，我们定义它的多线性型 Fχ\\mathcal F_\\chiFχ​ 为：
Fχ(RNDp(BP)):=sˉ⋅∏iDˉi,χinp(i)⋅tˉ−sˉ′⋅∏iDˉi,χinp(i)′⋅tˉ′(modp)\\mathcal F_\\chi(RND_p(BP)) := \\bar s \\cdot \\prod_i \\bar D_{i,\\chi_{inp(i)}} \\cdot \\bar t - \\bar s' \\cdot \\prod_i \\bar D'_{i,\\chi_{inp(i)}} \\cdot \\bar t' \\pmod{p} Fχ​(RNDp​(BP)):=sˉ⋅i∏​Dˉi,χinp(i)​​⋅tˉ−sˉ′⋅i∏​Dˉi,χinp(i)​′​⋅tˉ′(modp)

易知，当 Cx(y)=0C_x(y)=0Cx​(y)=0 时 $BP(\chi )=I$，此时以 $Pr=1$ 的概率 Fχ(RNDp(BP))=0\\mathcal F_\\chi(RND_p(BP))=0Fχ​(RNDp​(BP))=0。而当 Cx(y)≠0C_x(y)\\neq0Cx​(y)=0 时 $BP(\chi )\ne I$，此时以 $Pr=1-1/p$ 的概率 Fχ(RNDp(BP))≠0\\mathcal F_\\chi(RND_p(BP))\\neq0Fχ​(RNDp​(BP))=0。

现在，我们定义部分赋值的 RBP 程序（Garbled Branching Programs）。定义赋值函数为 σ:J→{0,1},J⊆[l]\\sigma:J \\to \\{0,1\\}, J \\subseteq [l]σ:J→{0,1},J⊆[l]，接着从 RBP 中移除 i∈IJ,b≠σ(inp(i))i \\in I_J,b \\neq \\sigma(inp(i))i∈IJ​,b=σ(inp(i)) 的那些矩阵 Di,b,Di,b′D_{i,b},D'_{i,b}Di,b​,Di,b′​，程序如下：

其中 $(J,\sigma )$ 是一组部分赋值，如果 $BP$ 计算的原始函数为 $F$，那么现在它所计算的函数为 F∣σF|_\\sigmaF∣σ​。对于不同的赋值 (J,σ0),(J,σ1)(J,\\sigma_0),(J,\\sigma_1)(J,σ0​),(J,σ1​)，如果 F∣σ0=F∣σ1F|_{\\sigma_0} = F|_{\\sigma_1}F∣σ0​​=F∣σ1​​，我们称两个部分赋值是关于 $F$ 功能等价的（functionally equivalent）。

GGH+13 做了一个 Equivalent Program Indistinguishability 假设：任意的 $n$ 长 BP 程序可计算函数 F:{0,1}l→{0,1}F:\\{0,1\\}^l \\to \\{0,1\\}F:{0,1}l→{0,1}，以及任意部分赋值 (J,σ0),(J,σ1)(J,\\sigma_0),(J,\\sigma_1)(J,σ0​),(J,σ1​)，如果它们是功能等价的，那么它们的 garbled programs 是计算不可区分的，
GARBLE(RND‾p(BP),(J,σ0))≡cGARBLE(RND‾p(BP),(J,σ1))GARBLE(\\overline{RND}_p(BP),(J,\\sigma_0)) \\overset{c}{\\equiv} GARBLE(\\overline{RND}_p(BP),(J,\\sigma_1)) GARBLE(RNDp​(BP),(J,σ0​))≡cGARBLE(RNDp​(BP),(J,σ1​))

根据上述假设，就可以构造出电路类 NC1NC^1NC1 上的不可区分混淆器 $i\mathcal{O}$：

1. 对于固定常数 $c$，任意安全参数 $\lambda$，电路簇 Cλ\\mathcal C_\\lambdaCλ​ 包含所有的深度为 $c\log \lambda$ 大小至多为 $\lambda$ 的电路，令 UλU_\\lambdaUλ​ 是通用电路，Uλ(C,m)=C(m),∀C∈CλU_\\lambda(C,m)=C(m),\\forall C \\in \\mathcal C_\\lambdaUλ​(C,m)=C(m),∀C∈Cλ​，其中 $C$ 是长度 $l(\lambda )$ 的电路描述。

2. 将通用电路 UλU_\\lambdaUλ​ 转化为 universal branching program UBPλ(C,m)UBP_\\lambda(C,m)UBPλ​(C,m)，令混淆器的输入 $C$ 对应的矩阵指标集为 ICI_CIC​，电路 $C$ 的一组赋值为 σC\\sigma_CσC​，那么定义不可区分混淆器为
   iO(λ,C):=GARBLE(RND‾p(UBPλ),(IC,σC))i\\mathcal O(\\lambda,C) := GARBLE(\\overline{RND}_p(UBP_\\lambda),(I_C,\\sigma_C)) iO(λ,C):=GARBLE(RNDp​(UBPλ​),(IC​,σC​))

3. 对于不同的两个有相同功能的电路 UBPλ(C1,⋅),UBPλ(C2,⋅)UBP_\\lambda(C_1,\\cdot), UBP_\\lambda(C_2,\\cdot)UBPλ​(C1​,⋅),UBPλ​(C2​,⋅)，根据 Equivalent Program Indistinguishability 的假设，iO(λ,C1)≡ciO(λ,C2)i\\mathcal O(\\lambda,C_1) \\overset{c}{\\equiv} i\\mathcal O(\\lambda,C_2)iO(λ,C1​)≡ciO(λ,C2​)，混淆后两者计算不可区分。