两方计算中的统计安全与协议分析

# 两方计算中的统计安全与协议分析 ## 1. 条件披露秘密（CDS）协议 ### 1.1 CDS协议流程 在CDS协议中，发送者和接收者进行一系列操作以实现秘密的条件披露。具体流程如下： 1. **发送者操作** - 电路加密：发送者将电路 $C$ 进行加密，得到 $(GC, lab) \leftarrow Garble.Gb(1^{\kappa}, C)$。 - 计算消息对：对于 $i \in [n]$，计算 $(m_{i0}, m_{i1}) = SSPOT.OTS(SSPOT.st_{iS}, cds_{i3})$。 - 处理标签：解析 $lab = \{lab_{0i}, lab_{1i}\}_{i\in [n+\ell]}$，对于 $i \in [n], \alpha \in \{0, 1\}$，计算 $y_{\alpha i} = m_{\alpha i} \oplus lab_{\alpha i}$，并设置 $y = \{y_{0i}, y_{1i}\}_{i\in [n]}$。 - 计算线标签：计算对应输入 $ptxt \in \{0, 1\}^{\ell}$ 的线标签 $L_i = Garble.En(ptxt_i, \{lab_{0(n+i)}, lab_{1(n+i)}\})$ ，其中 $i \in [\ell]$。 - 发送消息：发送 $cds_4 = (GC, y, \{L_i\}_{i\in [\ell]})$ 给接收者。 2. **接收者操作** - 恢复标签：对于 $i \in [n]$，计算 $lab_{i}' = m_{i}' \oplus y_{w_{i}i}$。 - 设置标签：设置 $lab_{(n+i)}' = L_i$，其中 $i \in [\ell]$。 - 评估电路：评估加密电路 $GC$，得到 $ptxt' = Garble.Ev(GC, \{lab_{i}'\}_{i\in [n+\ell]})$，并输出 $ptxt'$ 作为解密消息。 ### 1.2 CDS协议正确性与定理 CDS协议的正确性在于，接收者通过第 $i$ 个OT协议获得 $lab_{i}' = lab_{w_{i}i}$，当 $R(x, w) = 1$ 时，评估加密电路 $GC$ 可得到消息 $ptxt' == ptxt$。 定理表明，假设 $SSPOT$ 是一个四轮OT协议，具有针对恶意接收者的统计发送者隐私和针对半诚实发送者的计算接收者隐私，且 $Garble$ 是用于 $NC_1$ 电路的信息论加密方案，那么 $CDS$ 是用于可由 $NC_1$ 电路计算的关系 $R(x, \cdot)$ 验证的语句 $x \in L$ 的条件披露秘密协议。此外，它还提供针对恶意接收者的接收者模拟和针对半诚实发送者的消息不可区分性。 ## 2. 协议 $\pi_{mal}$ ### 2.1 协议 $\pi_{mal}$ 构造 协议 $\pi_{mal}$ 是将一个可解释的两方计算协议 $\pi_{exp}$ 编译为能抵抗恶意破坏的协议。接收者 $R$ 输入 $A$，发送者 $S$ 输入 $B$，协议 $\pi_{mal} = (R_1, S_1, R_2, S_2, R_3, S_3)$ 的具体步骤如下： #### 2.1.1 $R_1(1^{\kappa}, A)$ 1. 采样随机数 $r_R \leftarrow \{0, 1\}^*$，根据可解释协议计算 $\pi_{1exp} = \pi_{exp}.R_1(A; r_R)$。 2. 设置零知识证明（ZKP）和统计零知识论证（SZK）的第一条消息：$(z_1, st_{ZKP,P}) \leftarrow ZKP.P(1^{\kappa})$ 和 $(z_1', st_{SZK,V}) \leftarrow SZK.V_1(1^{\kappa})$。 3. 设置条件披露秘密（CDS）方案的第一条消息：$(cds_1, st_{CDS,R}) = CDS.CDS_1(1^{\kappa})$。 4. 发送 $\pi_{1mal} = (\pi_{1exp}, z_1, z_1', cds_1)$。 5. 存储状态 $st_R = (A, r_R, st_{ZKP,P}, st_{SZK,V}, st_{CDS,R})$。 #### 2.1.2 $S_1(1^{\kappa}, B, \pi_{1mal})$ 1. 采样随机数 $r_S \leftarrow \{0, 1\}^*$，根据可解释协议设置 $\pi_{2exp} = \pi_{exp}.S_1(\pi_{1exp}, B; r_S)$。 2. 设置ZKP和SZK的第二条消息：$(z_2, st_{ZKP,V}) \leftarrow ZKP.V_1(z_1, 1^{\kappa})$ 和 $(z_2', st_{SZK,P}) \leftarrow SZK.P_1(z_1')$。 3. 采样随机数 $r_{CDS,S} \leftarrow \{0, 1\}^*$，计算CDS方案的第二条消息：$(cds_2, st_{CDS,S}) = CDS.CDS_2(r_{CDS,S}, cds_1)$。 4. 发送 $\pi_{2mal} = (\pi_{2exp}, z_2, z_2', cds_2)$。 5. 存储状态 $st_S = (B, r_S, st_{ZKP,V}, st_{SZK,P}, st_{CDS,S})$。 #### 2.1.3 $R_2(st_R, \pi_{2mal})$ 1. 计算 $\pi_{3exp} = \pi_{exp}.R_2(\pi_{2exp}, A; r_R)$，设置语句 $x_{CDS} = (\pi_{1exp}, \pi_{2exp}, \pi_{3exp})$ 和见证 $w_{CDS} = (A, r_R, ldp)$，其中 $ldp$ 是 $(\pi_{1exp} = \pi_{exp}.R_1(A; r_R) \land \pi_{3exp} = \pi_{exp}.R_2(\pi_{2exp}, A; r_R))$ 的低深度证明。 2. 计算CDS方案的第三条消息：$(cds_3, st_{CDS,R}) \leftarrow CDS.CDS_3(1^{\kappa}, (x_{CDS}, w_{CDS}), st_{CDS,R}, cds_2)$。 3. 计算ZKP和SZK的第三条消息：$(z_3, st_{ZKP,P}) \leftarrow ZKP.P_2(z_2, st_{ZKP,P})$ 和 $(z_3', st_{SZK,V}) \leftarrow SZK.V_2(z_2', st_{SZK,V})$。 4. 发送 $\pi_{3mal} = (\pi_{3exp}, z_3, z_3', cds_3)$。 5. 更新状态 $st_R = (A, r_R, st_{ZKP,P}, st_{SZK,V}, st_{CDS,R})$。 #### 2.1.4 $S_2(st_S, \pi_{3mal})$ 1. 设置 $\pi_{4exp} = \pi_{exp}.S_2(\pi_{3exp}, B; r_S)$。 2. 设置语句 $x_{CDS} = (\pi_{1exp}, \pi_{2exp}, \pi_{3exp})$，计算CDS响应 $cds_4 \leftarrow CDS.CDS_4(r_{CDS,S}, (x_{CDS}, \pi_{4exp}), st_{CDS,S}, cds_3)$。 3. 计算ZKP的第四条消息：$(z_4, st_{ZKP,V}) \leftarrow ZKP.V_2(z_3, st_{ZKP,V})$。 4.