Chapter 9 恶意安全性：GMW 编译器与切分选择¶

半诚实 V.S. 恶意

半诚实（Semi-Honest）：按协议执行，但记录所有信息
恶意（Malicious）：可以任意偏离协议，包括错误消息、替换输入、选择性中止

本章核心技术路线

GMW 编译器：把任意半诚实协议编译成恶意安全协议，通用但效率较低
Cut-and-Choose：专门强化姚氏混淆电路
恶意 BGW：适合诚实多数下的信息论安全，典型门限是 $t < n/3$
BDOZ / SPDZ：基于 MAC 与预处理的高效通用 MPC，适合现代高性能实现

1 零知识证明¶

NP 关系与陈述

关系 $\mathcal{R} \subseteq \{0,1\}^* \times \{0,1\}^*$，语言 $L_{\mathcal{R}} = \{x \mid \exists w,\ (x, w) \in \mathcal{R}\}$
陈述（statement） 为 $x$，见证（witness） 为 $w$

两方协议 $(P, V)$：证明者 $P(x, w)$ 与验证者 $V(x)$ 交互
目标：$P$ 证明 $x \in L_{\mathcal{R}}$，要求
- 完备性（Completeness）：若 $(x,w)\in R$ 且双方诚实，则验证者接受
- 可靠性 / 声明正确性（Soundness）：若证明被接受，则陈述必须为真
- 零知识性（Zero-Knowledge）：验证者除了陈述为真外得不到额外信息

2 Sigma 协议¶

对关系 $R$ 的 Sigma 协议由三部分组成：

$a \leftarrow C(x,w;r)$：证明者发送初始消息
$z \leftarrow Z(x,w,r,e)$：验证者给出挑战 $e$ 后，证明者回复
$V(x,a,e,z)\in\{0,1\}$：验证者检查

Sigma 协议要求满足：

完备性：对于所有 $(x, w) \in \mathcal{R}$，$e \in \{0, 1\}^\lambda$，有

\[ \Pr\left[ a \leftarrow C(x, w; r);\ z \leftarrow Z(x, w, r, e):\ \mathcal{V}(x, a, e, z) = 1 \right] = 1 \]
2-特殊可靠性（2-special soundness）：存在确定性多项式时间提取器 $\mathcal{X}$，使得对任意 PPT 的敌手 $\mathcal{A}$ 都有

\[ \Pr\left[ \begin{aligned} &(x, a) \leftarrow \mathcal{A}(1^\lambda);\ e, e' \xleftarrow{\$} \{0, 1\}^\lambda; \\ &z, z' \leftarrow \mathcal{A}(e, e');\ w \leftarrow \mathcal{X}(x, a, \{e, z\}, \{e', z'\}) \end{aligned} :\ \begin{aligned} &e \neq e' \land \mathcal{V}(x, a, e, z) = 1 \land \\ &\mathcal{V}(x, a, e', z') = 1 \land (x, w) \notin \mathcal{R} \end{aligned} \right] = 0 \]
诚实验证者零知识性（HVZK）：存在 PPT 的算法 $\mathcal{S}$，使得对任意 PPT 的敌手 $\mathcal{A}$ 都有

\[ \begin{aligned} \Pr\left[ (x, e) \leftarrow \mathcal{A}(1^\lambda);\ a \leftarrow C(x, w; r);\ z \leftarrow Z(x, w, r, e):\ \mathcal{A}(a, z) = 1 \right] \\ \approx \Pr\left[ (x, e) \leftarrow \mathcal{A}(1^\lambda);\ (a, z) \leftarrow \mathcal{S}(x, e):\ \mathcal{A}(a, z) = 1 \right] \end{aligned} \]

其中 $r$ 是均匀随机选取的，$\mathcal{A}$ 输出的值必须满足 $(x, w) \in \mathcal{R}$ 和 $e \in \{0, 1\}^\lambda$

示例

步骤说明

随机取 $m',s',t'$
发送

\[ a_1 = g^{m'}ck^{s'},\quad a_2 = g^{t'},\quad a_3 = g^{m'}pk^{t'} \]
接收挑战 $e$
回复

\[ z_1 = m' + em,\quad z_2 = s' + es,\quad z_3 = t' + et \]

验证者检查：

\[ g^{z_1}ck^{z_2}=a_1c^e,\qquad g^{z_3}=a_2c_1^e,\qquad g^{z_1}pk^{z_3}=a_3c_2^e. \]

完备性证明

\[ \begin{align*} a_1 c^e &= g^{m'} ck^{s'} \cdot \left(g^m ck^s\right)^e = g^{m' + em} ck^{s' + es} = g^{z_1} ck^{z_2}\\ a_2 c_1^e &= g^{t'} \cdot \left(g^t\right)^e = g^{t' + et} = g^{z_3}\\ a_3 c_2^e &= g^{m'} pk^{t'} \cdot \left(g^m pk^t\right)^e = g^{m' + em} pk^{t' + et} = g^{z_1} pk^{z_3} \end{align*} \]

2-特殊可靠性证明

如果对于初始消息 $a_1, a_2, a_3$，有 $(e, z_1, z_2, z_3)$ 和 $(e', z_1', z_2', z_3')$ 都能通过验证，根据验证等式，有：

\[ \begin{aligned} g^{z_1} ck^{z_2} &= a_1 \cdot c^e, & g^{z_3} &= a_2 \cdot c_1^e, & g^{z_1} pk^{z_3} &= a_3 \cdot c_2^e, \\ g^{z_1'} ck^{z_2'} &= a_1 \cdot c^{e'}, & g^{z_3'} &= a_2 \cdot c_1^{e'}, & g^{z_1'} pk^{z_3'} &= a_3 \cdot c_2^{e'}. \end{aligned} \]

因此：

\[ \begin{aligned} c &= g^{(z_1 - z_1')(e - e')^{-1}} ck^{(z_2 - z_2')(e - e')^{-1}}, \\ c_1 &= g^{(z_3 - z_3')(e - e')^{-1}}, \\ c_2 &= g^{(z_1 - z_1')(e - e')^{-1}} pk^{(z_3 - z_3')(e - e')^{-1}}. \end{aligned} \]

可以提取见证：

\[ m = (z_1 - z_1')(e - e')^{-1},\ s = (z_2 - z_2')(e - e')^{-1},\ t = (z_3 - z_3')(e - e')^{-1} \]

满足：

\[ c = g^m ck^s \land c_1 = g^t \land c_2 = g^m pk^t. \]

诚实验证者零知识性证明

模拟器可先随机取 $z_1,z_2,z_3$，再反推出

\[ a_1=\frac{g^{z_1}ck^{z_2}}{c^e},\quad a_2=\frac{g^{z_3}}{c_1^e},\quad a_3=\frac{g^{z_1}pk^{z_3}}{c_2^e}, \]

得到与真实会话同分布的 transcript

3 GMW 编译器¶

把任意半诚实安全协议编译成恶意安全协议，强制每个参与方在每一步都证明自己确实像半诚实方那样在做。

输入承诺（Input Commitment）：每个参与方对输入 $x_i$ 与随机数 $\rho_i$ 做承诺 $c_i = Com(x_i,\rho_i)$
抛硬币（Coin Tossing）：每个参与方 $P_i$ 承诺随机数 $r_{i,i}$，其他参与方各自承诺 $r_{i,j}$，打开后令 $r_i = \bigoplus_{j=1}^{n} r_{i,j}$，只要有一方诚实，$r_i$ 就仍然均匀随机
逐步零知识证明（ZK for Every Message）：当 $P_i$ 发送任意协议消息 $m$ 时，同时证明 $m$ 确实是由已承诺输入 $x_i$、随机带 $r_i$ 以及历史消息，按照原半诚实协议诚实计算得到的

4 切分选择（Cut-and-Choose）¶

4. 1 概述¶

引入

姚氏混淆电路在半诚实模型下安全，但在恶意模型中，若电路生成方 $P_1$ 发送错误电路 $C'$，可能直接泄露 $P_2$ 输入。

$P_1$ 生成 $s$ 个混淆电路副本，$P_2$ 随机选择其中 $s/2$ 个作为检查电路，要求打开并验证这些电路，剩下 $s/2$ 个作为计算电路，对计算电路求值，并对结果做多数投票。

欺骗成功概率

badTotal：坏电路总数
noAbort：所有检查电路都正确
badMaj：计算电路中坏电路至少占一半

\[ \Pr[\text{noAbort} \land \text{badMaj}] = \sum_{i=s/4}^{s/2} \Pr[\text{noAbort} \land \text{badTotal} = i]. \]

当 $\text{badTotal} = i$ 时，$\text{noAbort}$ 发生需从 $s-i$ 个正确电路中选出 $\frac{s}{2}$ 个：

\[ \Pr[\text{noAbort} \mid \text{badTotal} = i] = \frac{\binom{s-i}{s/2}}{\binom{s}{s/2}}. \]

因此

\[ \begin{aligned} \Pr[\text{noAbort} \land \text{badMaj}] &\le \sum_{i=s/4}^{s/2} \frac{\binom{s-i}{s/2}}{\binom{s}{s/2}} = \frac{1}{\binom{s}{s/2}} \sum_{i=s/4}^{s/2} \binom{s-i}{s/2}. \end{aligned} \]

令 $j = s-i$，并使用恒等式 $\sum_{k=0}^{n} \binom{k}{m} = \binom{n+1}{m+1}$，得

\[ \Pr[\text{noAbort} \land \text{badMaj}] = \frac{\binom{\frac{3s}{4}+1}{\frac{s}{2}+1}}{\binom{s}{s/2}} = \frac{(\frac{3s}{4}+1)!}{(\frac{s}{2}+1)!(\frac{s}{4})!} \cdot \frac{(\frac{s}{2})!(\frac{s}{2})!}{s!} = \frac{(\frac{s}{2})(\frac{s}{2}-1)\cdots(\frac{s}{4}+1)}{s(s-1)\cdots(\frac{3s}{4}+2)} \cdot \frac{1}{\frac{s}{2}+1} \]

令 $t = s/4$，则

\[ \frac{2t}{4t} \cdot \frac{2t-1}{4t-1} \cdots \frac{t+2}{3t+2} \cdot \frac{t+1}{2t+1} = \left( \prod_{i=2}^{t} \frac{t+i}{3t+i} \right) \cdot \frac{t+1}{2t+1}. \]

因 $\frac{t+i}{3t+i} < \frac{1}{2}$（对所有 $i < t$），故 $$ \Pr[\text{noAbort} \land \text{badMaj}] < \frac{1}{2^{t-1}} = \frac{1}{2^{s/4-1}}. $$

例如取 $s=164$，则该概率 $< 2^{-40}$

为什么不能发现输出不一致就直接中止？

若 $P_1$ 只在某个特殊输入位上让一个电路输出错误，那么若 $P_2$ 看到输出不一致就立即中止，$P_1$ 便能通过是否中止学到该输入位。

因此正确做法是继续对所有计算电路求值，并取多数输出。

4. 2 输入一致性（Input Consistency）¶

若 $P_1$ 在不同计算电路里使用不同输入，就能跨电路编程泄露 $P_2$ 的隐私。

示例：内积泄露

对功能

\[ f(x,y)=\langle x,y\rangle=\sum_i x_i y_i, \]

若 $P_1$ 在第 $i$ 个电路里只令第 $i$ 位为 $1$，其他位为 $0$，那么不同电路输出就携带了关于 $y_i$ 的信息。

对每条输入导线，把所有电路里的 0/1 输入密钥分别承诺成两个集合
在检查电路上打开相应承诺并验证
在计算电路上做零知识证明，证明“发送的所有密钥都来自同一个集合”

4. 3 选择性中止（Selective Abort / Failure）¶

若在 OT 中，$P_1$ 本应发送 $(k_i^0, k_i^1)$，却恶意发送 $(k_i^0,0)$，则当 $P_2$ 输入位为 $0$ 时正常，当输入位为 $1$ 时协议中止，于是 $P_1$ 能从“是否中止”恢复 $P_2$ 的输入位。

防御

committing OT：OT 同时绑定 $P_1$ 的输入，抽检电路时一并打开并验证。
cut-and-choose OT / CCOT：抽检索引直接暴露两条 OT 输入，迫使 $P_1$ 在大多数 OT 中诚实。

核心目标都是让发送方在抽检时必须为其 OT 输入负责。

4. 4 输出真实性（Output Authenticity）¶

公平性一般无法完全实现，但可以要求若某方先拿到输出并转发给另一方，那么接收方能验证该输出的真实性。

基于 MAC 的构造

取域 $\mathbb{F}$，随机选

\[ p,a,b \xleftarrow{}_{\$}\mathbb{F} \]

并定义单输出功能返回：

\[ \alpha = p + f_1(x,y),\qquad \beta = a\alpha + b. \]

让先输出的一方发送 $(\alpha,\beta)$，另一方验证

\[ \beta = a\alpha + b \]

后再恢复真实输出

\[ f_1(x,y)=\alpha-p. \]

其中 $p$ 起到一次一密作用，伪造 MAC 的成功概率约为 $1/|\mathbb{F}|$。

5 LP11 协议¶

引入

Lindell 和 Pinkas 在 2011 年提出的切分选择协议进行了以下改进：

以 CCOT 代替 committing OT：
- 接收方输入选择比特 $\sigma_1, \dots, \sigma_s$ 与集合 $\mathcal{J} \subset [s], |\mathcal{J}| = s/2$；对 $i \in [s]$ 得到 $x_i^{\sigma_i}$，对 $j \in \mathcal{J}$ 得到 $(x_j^0, x_j^1)$。
- $\mathcal{J}$ 即要打开的电路索引，CCOT 将 OT 与切分选择检查合并，有效抵御选择性中止攻击。
高效输入一致性证明：
- 设输入长度为 $\ell$，选取 $\{g^{a_i^0}, g^{a_i^1}\}_{i=1}^\ell$ 与 $\{g^{r_j}\}_{j=1}^s$，设置第 $j$ 个电路第 $i$ 位密钥为 $g^{a_i^0 r_j}, g^{a_i^1 r_j}$。
- 在 DDH 假设下，已知 $\{g^{a_i^0}, g^{a_i^1}, g^{r_j}\}$ 与实际输入对应密钥时，其余密钥仍伪随机，从而使一致性 ZK 证明更高效。

5. 1 CCOT 理想功能¶

切分选择 OT 理想功能 $F_{CCOT}$

发送方输入：$s$ 对消息 $\bar{x}=\{(x_i^0,x_i^1)\}_{i=1}^{s}$
接收方输入：选择比特 $\sigma_1,\dots,\sigma_s\in\{0,1\}$，以及集合 $J\subseteq[s]$
若 $|J|\ne s/2$，双方输出 $\bot$
若 $|J|=s/2$：
- 对 $j\in J$，接收方获得两条消息 $(x_j^0,x_j^1)$，用于打开检查电路
- 对 $j\notin J$，接收方只获得 $x_j^{\sigma_j}$，用于计算电路

单一选择 CCOT $F_{CCOT}^{S}$：接收方只有一个选择位 $\sigma$，对所有 $j\notin J$ 都获得 $x_j^\sigma$
批处理单一选择 CCOT $F_{CCOT}^{S,B}$：发送方输入 $\ell$ 个长度为 $s$ 的消息对向量，接收方输入 $\ell$ 个选择位 $\sigma_1,\dots,\sigma_\ell$ 和同一个检查集合 $J$

5. 2 PVW 型 DDH OT 构造¶

协议步骤说明

接收方取 $y,\alpha_0\xleftarrow{}_{\$}\mathbb{Z}_q$，令 $\alpha_1=\alpha_0+1$，

\[ g_1=g_0^y,\qquad h_0=g_0^{\alpha_0},\qquad h_1=g_1^{\alpha_1} \]

并向发送方发送 $(g_1,h_0,h_1)$，再用 ZK 证明相关元组满足“非 DH”约束，保证自己不能同时解两条消息。
接收方取 $r\xleftarrow{}_{\$}\mathbb{Z}_q$，发送

\[ \tilde{g}=(g_\sigma)^r,\qquad \tilde{h}=(h_\sigma)^r \]
发送方定义随机化函数

\[ RAND(w,x,y,z)=(u,v)=(w^s y^t,\ x^s z^t) \]

其中 $s,t\xleftarrow{}_{\$}\mathbb{Z}_q$，并计算

\[ (u_b,v_b)=RAND(g_b,\tilde{g},h_b,\tilde{h}),\qquad w_b=v_b\cdot x_b \]
接收方恢复

\[ x_\sigma=\frac{w_\sigma}{(u_\sigma)^r} \]

正确性：$\frac{w_\sigma}{(u_\sigma)^r}=\frac{v_\sigma \cdot x_\sigma}{(u_\sigma)^r}=\frac{g^s \cdot h^t \cdot x_\sigma}{\left( (g_\sigma)^s \cdot (h_\sigma)^t \right)^r}=\frac{g^s \cdot h^t \cdot x_\sigma}{g^s \cdot h^t}=x_\sigma$

DH 元组的零知识证明协议

安全直觉

若 $(g_0,g_1,h_0,h_1)$ 不是 DH 元组，$RAND$ 使至少一侧密文看起来均匀随机，接收方只能解一条消息
若接收方能构造成 DH 元组并知道 $y=\log_{g_0}g_1$，则可能解出两条消息，因此需要 ZK 证明排除这类作弊
- 对 $\sigma = 0$，接收方已得 $x_0$，并可计算 $x_1 = \frac{w_1}{(u_1)^{ry^{-1}}} = \frac{g^s h^t x_1}{\left((g_1)^s (h_1)^t\right)^{ry^{-1}}} = \frac{g^s h^t x_1}{\left((g_0)^s (h_0)^t\right)^r} = x_1$
- 同理 $\sigma = 1$ 时，可由 $w_0 / (u_0)^{ry}$ 得到 $x_0$
模拟器在发送方被攻陷时可把元组设成可提取形式，在接收方被攻陷时可通过 ZK 提取其选择位
- 发送方 $P_s$ 被攻陷：模拟器 $S$ 令 $\alpha_1 = \alpha_0$（使元组为 DH），并伪造零知识证明，从而提取 $P_s$ 的两个输入
- 接收方 $P_r$ 被攻陷：模拟器 $S$ 通过零知识证明提取见证 $\alpha_0$，计算 $\alpha_1 = \alpha_0 + 1$。比较 $h = g^{\alpha_0}$ 或 $h = g^{\alpha_1}$，即可恢复选择比特 $\sigma$

子集是 DH 元组的零知识证明协议

5. 3 CCOT 协议与批处理¶

CCOT 协议思路

准备阶段：接收方为每个 $j\in[s]$ 构造 $(h_{j,0},h_{j,1})$；对 $j\in J$ 构造可打开两侧的结构，对 $j\notin J$ 构造只能打开一侧的结构
集合证明：接收方零知识证明“恰有 $s/2$ 个位置对应检查集合”，防止事后改变 $J$
传输阶段：对每个 $j$ 并行运行 PVW 型传输；$j\in J$ 可恢复两条消息，$j\notin J$ 只能恢复所选消息

批处理单一选择版本只运行一次准备阶段，对每个输入位 $i\in[\ell]$ 并行运行传输阶段，使所有输入位共享同一个检查集合 $J$，从而和 Cut-and-Choose 电路划分保持一致。

批处理单一选择切分选择 OT 理想功能 $\mathcal{F}_{\text{CCOT}}^{S,B}$

输入：
- 发送方 $P_s$ 的输入是 $\ell$ 个长度为 $s$ 的向量 $\vec{x}_i$, $i \in [\ell]$（每个向量由 $s$ 对消息构成）。
- 接收方 $P_r$ 的输入是 $\ell$ 个选择比特 $\sigma_1, \dots, \sigma_\ell \in \{0, 1\}$ 和大小为 $s/2$ 的集合 $\mathcal{J} \subseteq [s]$。
输出：如果 $\mathcal{J}$ 的大小不是 $s/2$，$P_s$ 和 $P_r$ 的输出为 $\perp$。否则：
- 对于 $i \in [\ell]$ 和 $j \in \mathcal{J}$，接收方 $P_r$ 获得 $\vec{x}_i$ 的第 $j$ 对消息。
- 对于 $i \in [\ell]$ 和 $j \notin \mathcal{J}$，接收方 $P_r$ 获得 $\vec{x}_i$ 的第 $j$ 对消息的第 $\sigma_i$ 个值（$\sigma_i \in \{0, 1\}$，这里的第 $\sigma_i$ 个值从 0 开始计数）。

5. 4 输入一致性零知识证明¶

给定陈述

\[ (G,g_0,g_1,g',u_1,v_1,\dots,u_s,v_s,h_1,\dots,h_s), \]

证明者要证明存在同一个 $r$，使得二者之一成立：

\[ g'=(g_0)^r\ \land\ \forall j,\ h_j=(u_j)^r, \]

或

\[ g'=(g_1)^r\ \land\ \forall j,\ h_j=(v_j)^r. \]

第一种对应输入位为 $0$，第二种对应输入位为 $1$；因此通过证明就能保证所有计算电路使用同一个输入比特。

压缩证明技巧

验证者随机取 $\gamma_1,\dots,\gamma_s$，双方本地计算

\[ \tilde{u}=\prod_{j=1}^{s}u_j^{\gamma_j},\qquad \tilde{v}=\prod_{j=1}^{s}v_j^{\gamma_j},\qquad \tilde{h}=\prod_{j=1}^{s}h_j^{\gamma_j}. \]

然后证明 $(g_0,g',\tilde{u},\tilde{h})$ 或 $(g_1,g',\tilde{v},\tilde{h})$ 是 DH 元组。随机线性组合把 $s$ 个等式压缩成一个等式，降低证明成本。

5. 5 LP11 协议¶

公共输入：统计安全参数 $s$、函数 $f$ 对应的布尔电路 $C$、群参数 $(G,q,g)$，其中 $G$ 是阶为 $q$、以 $g$ 为生成元的循环群
私有输入：$P_1$ 输入 $x\in\{0,1\}^{\ell}$，$P_2$ 输入 $y\in\{0,1\}^{\ell}$

协议步骤说明

构造 $s$ 个混淆电路：
- $P_1$ 选择随机值 $a_1^0, a_1^1, \dots, a_\ell^0, a_\ell^1 \xleftarrow{\$} \mathbb{Z}_q$ 和 $r_1, \dots, r_s \xleftarrow{\$} \mathbb{Z}_q$
- 设 $w_1, \dots, w_\ell$ 是 $P_1$ 在电路 $C$ 中的输入导线，用 $w_{i,j}$ 表示第 $j$ 个混淆电路中的导线 $w_i$，用 $k_{i,j}^b$ 表示导线 $w_{i,j}$ 对应于比特 $b$ 的密钥，$P_1$ 将这些输入导线的密钥设置为
  
  \[ k_{i,j}^0 = H(g^{a_i^0 \cdot r_j}),\ k_{i,j}^1 = H(g^{a_i^1 \cdot r_j}) \]
  
  其中，$H$ 是一个随机数提取器。
- $P_1$ 用这些密钥构造 $s$ 个混淆电路 $GC_1, \dots, GC_s$
- 用这些密钥构造 $GC_1,\dots,GC_s$
茫然传输：$P_1$ 和 $P_2$ 以参数 $\ell$ 和 $s$ 执行批处理单一选择切分选择 OT
- $P_1$ 定义向量 $\vec{z}_1, \dots, \vec{z}_\ell$，其中 $\vec{z}_i$ 包含了 $P_2$ 的输入比特 $y_i$ 在 $GC_1, \dots, GC_s$ 中的 $s$ 对密钥
- $P_2$ 的输入是大小为 $s/2$ 的随机集合 $\mathcal{J} \subset [s]$ 和 $\sigma_1, \dots, \sigma_\ell \in \{0,1\}$，其中 $\sigma_i = y_i,\ i \in [\ell]$。
- 对于 $GC_j,\ j \in \mathcal{J}$，$P_2$ 获得他的输入导线的两个密钥；对于其他电路，$P_2$ 获得他的输入对应的密钥。
发送电路和承诺：$P_1$ 向 $P_2$ 发送 $s$ 个混淆电路，随机数提取器 $H$ 的定义，以及 $P_1$ 的输入导线密钥的承诺 $\{(i,0,g^{a_i^0}),(i,1,g^{a_i^1})\}_{i=1}^\ell$，$\{(j,g^{r_j})\}_{j=1}^s$。
发送切分选择挑战：$P_2$ 向 $P_1$ 发送集合 $\mathcal{J}$ 以及电路 $\{GC_j\}_{j\in\mathcal{J}}$ 中 $P_2$ 的第一个输入比特 $y_1$ 对应的两个密钥，如果密钥不正确，$P_1$ 输出 $\perp$ 并终止协议。
- $\{GC_j\}_{j\in\mathcal{J}}$ 称为检查电路，$\{GC_j\}_{j\notin\mathcal{J}}$ 称为计算电路。
打开检查电路随机性：对于每个检查电路 $GC_j$，$P_1$ 向 $P_2$ 发送 $r_j$，$P_2$ 检查该值与第 3 步中的 $(j,g^{r_j})$ 是否一致，如果不一致，$P_2$ 输出 $\perp$ 并终止协议。
验证检查电路正确性：
- 对于 $j\in\mathcal{J}$，$P_2$ 使用第 3 步得到的 $g^{a_i^0},g^{a_i^1}$ 和第 5 步得到的 $r_j$ 计算 $GC_j$ 中 $P_1$ 的输入导线密钥 $k_{i,j}^0 = H(g^{a_i^0\cdot r_j}),k_{i,j}^1 = H(g^{a_i^1\cdot r_j})$
- $P_2$ 将自己的输入导线密钥设置为切分选择 OT 中获得的值
- 已知所有的输入导线密钥，$P_2$ 解密所有的混淆表来检查混淆电路的正确性
- 如果存在不正确的混淆电路，$P_2$ 输出 $\perp$ 并终止协议
发送计算电路输入密钥并证明一致性：
- 对于 $j \notin \mathcal{J},\ i \in [\ell]$，$P_1$ 发送 $k_{i,j}' = g^{a_i^{x_i} \cdot r_j}$ 给 $P_2$，$P_2$ 设置 $k_{i,j} = H(k_{i,j}')$
- $P_1$ 证明输入密钥的一致性：对于 $i \in [\ell]$，$P_1$ 并行地证明存在 $\sigma_i \in \{0,1\}$ 使得 $k_{i,j}' = g^{a_i^{\sigma_i} \cdot r_j}$ 对 $j \notin \mathcal{J}$ 都成立，如果证明不通过，$P_2$ 输出 $\perp$ 并终止协议
计算并多数投票：
- $P_2$ 用第 7 步获得的 $P_1$ 的输入密钥和第 2 步获得的 $P_2$ 的输入密钥计算所有的计算电路 $\{GC_j\}_{j \notin \mathcal{J}}$
- 如果某个电路的计算失败了，$P_2$ 将其输入记为 $\perp$
- 最后，$P_2$ 取大多数电路的输出作为协议的输出

6 LP11 的安全性证明¶

证明目标

在 $\mathcal{F}_{\text{CCOT}}^{S,B}$-混合模型下，构造模拟器 $\mathcal{S}$，使得

\[ \left\{ \text{IDEAL}_{f,\mathcal{S}}(x,y,n,s) \right\}_{x,y\in\{0,1\}^\ell;\ n,s\in\mathbb{N}} \stackrel{\text{comp}}{\approx} \left\{ \text{REAL}_{\Pi,\mathcal{A}}(x,y,n,s) \right\}_{x,y\in\{0,1\}^\ell;\ n,s\in\mathbb{N}}. \]

检查电路都正确但计算电路多数错误 的概率必须可忽略
必须从第 7 步 ZK 中提取一致输入 $x$
模拟出的挑战集合 $J$、检查消息、承诺验证过程都要与真实分布一致

6. 1 情况 1：$P_1$ 被攻陷¶

模拟器的主要步骤

$S$ 内部运行敌手 $\mathcal{A}$（控制 $P_1$），记录其在 CCOT 中输入 $\{(z_0^{i,j}, z_1^{i,j})\}_{i\in[\ell],j\in[s]}$
记录 $P_1$ 发送的 $GC_1, \dots, GC_s$ 及承诺 $\{(i,0,u_i^0),(i,1,u_i^1)\}_{i=1}^\ell, \{(j,h_j)\}_{j=1}^s$
$S$ 均匀随机选取 $|\mathcal{J}| = s/2$，并模拟 $P_2$ 发送 $\mathcal{J}$ 与 $\{(z_0^{1,j}, z_1^{1,j})\}_{j\in\mathcal{J}}$（协议第 4 步）
记录 $\{r_j\}_{j\in\mathcal{J}}$，检查 $h_j \stackrel{?}{=} g^{r_j}$，若失败，向理想功能发送 $\perp$ 并终止
按协议检查 $\{GC_j\}_{j\in\mathcal{J}}$ 正确性，若失败则发送 $\perp$ 并终止
记录第 7(a) 步消息 $\{k_{i,j}'\}_{i\in[\ell],j\notin\mathcal{J}}$
从第 7(b) 步 ZK 证明提取见证 $a_i$，满足

\[ k_{i,j}' = (h_j)^{a_i}\ (j\notin\mathcal{J}),\quad u_i^0 = g^{a_i}\ \lor\ u_i^1 = g^{a_i}. \]

若任一 $i$ 提取失败，则发送 $\perp$ 并终止
对每个 $i\in[\ell]$，若 $u_i^0 = g^{a_i}$ 置 $x_i=0$，若 $u_i^1 = g^{a_i}$ 置 $x_i=1$，输出提取到的 $x=x_1\cdots x_\ell$ 给可信方，并输出 $\mathcal{A}$ 的输出

坏电路概率界

对每个电路 $GC_j$：

$P_1$ 输入导线密钥：$(g^{a_1^0 r_j}, g^{a_1^1 r_j}), \dots, (g^{a_\ell^0 r_j}, g^{a_\ell^1 r_j})$
$P_2$ 输入导线密钥：来自 CCOT 输入 $(z_0^{i,j}, z_1^{i,j})$

若这两部分密钥不能将 $GC_j$ 打开为正确布尔电路 $C$，则称 $GC_j$ 为坏电路，则有：

\[ \Pr[\text{noAbort} \land \text{badMaj}] \le \sum_{i=s/4}^{s/2} \frac{\binom{s-i}{s/2}}{\binom{s}{s/2}} = \frac{\binom{\frac{3s}{4}+1}{\frac{s}{2}+1}}{\binom{s}{s/2}} < 2^{-(s/4-1)} \]

条件于好事件（$\lnot(\text{noAbort} \land \text{badMaj})$）时：

ZK 提取失败概率为 $\text{negl}(n)$
提取到的输入 $x$ 与真实输入一致
多数计算电路输出为 $f(x,y)$
$S$ 对 $\mathcal{J}$ 与挑战消息的模拟分布与真实相同

总优势满足：

\[ \text{Adv}_\mathcal{D} \le \Pr[\text{noAbort} \land \text{badMaj}] + \text{negl}(n) \le 2^{-(s/4-1)} + \text{negl}(n) = \text{negl}(n,s). \]

因而 $P_1$ 被攻陷的情况下，REAL 与 IDEAL 计算不可区分。

6. 2 情况 2：$P_2$ 被攻陷¶

模拟器的主要步骤

$S$ 内部运行 $A$（控制 $P_2$），记录其向 $\mathcal{F}_{\text{CCOT}}^{S,B}$ 的输入 $\mathcal{J}$ 与 $\sigma_1,\dots,\sigma_\ell$。若 $|\mathcal{J}| \neq s/2$，则发送 $\perp$ 并终止。
随机选 $a_i^0, a_i^1 \xleftarrow{\$} \mathbb{Z}_q\ (i\in[\ell])$，$r_j \xleftarrow{\$} \mathbb{Z}_q\ (j\in[s])$，并构造密钥矩阵：

\[ (x_{i,j}^0, x_{i,j}^1) = \left(H(g^{a_i^0 r_j}), H(g^{a_i^1 r_j})\right) \]

对应 $P_1$ 输入导线，$P_2$ 输入导线密钥随机生成。
将该矩阵作为发送方输入喂给理想 CCOT，令 $A$ 获得一致输出，$j\in\mathcal{J}$ 得到两把密钥，$j\notin\mathcal{J}$ 得到 $\{x_{i,j}^{\sigma_i}\}_{i\in[\ell]}$
$S$ 发送 $y=\sigma_1\cdots\sigma_\ell$ 给可信方，得到功能输出 $z=f(x,y)$
对 $j \in \mathcal{J}$，诚实地构造检查电路 $GC_j$
对 $j \notin \mathcal{J}$，构造假电路 $\widetilde{GC}_j$，其输出恒为 $z$，输入导线密钥沿用前述矩阵
模拟发送电路与承诺 $\{(i,0,g^{a_i^0}),(i,1,g^{a_i^1})\}_{i=1}^\ell,\ \{(j,g^{r_j})\}_{j=1}^s$
记录 $A$ 发来的 $\mathcal{J}'$ 与密钥，检查：

\[ \mathcal{J}' \neq \mathcal{J} \land \text{两把密钥都正确} \Rightarrow \text{fail}, \]

密钥不正确则发送 $\perp$ 并终止；否则继续.
发送 $\{r_j\}_{j\in\mathcal{J}}$；对 $j\notin\mathcal{J}$ 发送 $k_{i,j}' = g^{a_i^0 r_j}$，并诚实地执行输入一致性 ZK（取 $x=0^\ell$）

失败概率界

fail 只会发生在$P_2$ 提交了 $J'\ne J$ 但仍然猜中了某个检查电路中自己本不该知道的两把正确密钥，因此：

\[ \Pr[\text{fail}] \le s\cdot 2^{-n} = negl(n) \]

CCOT 的单一选择约束保证 $P_2$ 无法在不同电路使用不一致输入。
因而 $P_2$ 视图中，主要差异仅是计算电路由真实电路替换为假电路。

设混合序列 $H_0, \dots, H_{s/2}$：$H_t$ 中前 $t$ 个计算电路被替换为假电路，其余保持真实。

\[ \left|\Pr\left[\mathcal{D}(H_0)=1\right] - \Pr\left[\mathcal{D}(H_{s/2})=1\right]\right| \le \sum_{t=1}^{s/2} \left|\Pr\left[\mathcal{D}(H_{t-1})=1\right] - \Pr\left[\mathcal{D}(H_t)=1\right]\right|. \]

每一项由姚电路安全性给出 $\text{negl}(n)$，故：

\[ \left|\Pr\left[\mathcal{D}(H_0)=1\right] - \Pr\left[\mathcal{D}(H_{s/2})=1\right]\right| \le \frac{s}{2} \cdot \text{negl}(n) = \text{negl}(n,s) \]

再结合 $\Pr[\text{fail}] = \text{negl}(n)$，得到：

\[ \{\text{IDEAL}_{f,\mathcal{S}}(x,y,n,s)\}_{x,y\in\{0,1\}^\ell; n,s\in\mathbb{N}} \stackrel{\text{comp}}{\approx} \{\text{REAL}_{\Pi,\mathcal{A}}(x,y,n,s)\}_{x,y\in\{0,1\}^\ell; n,s\in\mathbb{N}}. \]

因而 $P_2$ 被攻陷的情况下，REAL 与 IDEAL 计算也不可区分。

6. 3 从独立安全到 UC 安全¶

在 LP11 的证明中，只有“从零知识证明中提取见证”这一步显式依赖了倒带（rewinding），若把协议里的 Sigma 协议替换为 UC 安全零知识证明，则整个协议可提升到 UC 安全。

在 CRS（公共参考字符串）模型 和 DDH 假设 下，这种替换是可行的。

UC 安全性

对任意输入长度为 $\ell$ 的两方功能 $f$，在 CRS 模型和 DDH 假设下，存在协议 $\Pi$，可在静态恶意敌手下 UC-安全实现 $f$。