Pick up Lost Property on Secure 3-party Computation(2)

安全三方计算

另一方面，对于随机值的共享生成函数也是具有计算安全性的。各方能生成随机秘密值$v$的共享，但其它方不能知晓。定义功能函数$\mathcal{F}_{\text{rand}}$随机选择$v \in \{0,1 \}$，计算出共享$[v]$，并发送给其他发放共享。函数$\mathcal{F}_{\text{rand}}$允许腐败方决定他持有的共享，且用这个共享值计算诚实方的秘密共享，以及随机数$v$。函数$\mathcal{F}_{\text{rand}}$的构造如下：

在$\mathcal{F^2_\text{cr}}$混合函数$\mathcal{F}_{\text{rand}}$的构造如下，不存在任何交互：

显然，协议中$t_1 \oplus t_2 \oplus t_3 = 0$，此外，再定义$v = s_1 \oplus t_3 = r_1 \oplus r_2 \oplus r_3$，这里有 $ s_2 \oplus t_1 $和$ s_3 \oplus t_2 $的值都等于$v$。定义$\mathcal{F^2_\text{cr}}$，腐败方并不清楚均匀随机选择$ r_{i+1} = \alpha_{i+1}$，认为这些值具有随机性。这一步说明，如果协议2.9能安全计算功能函数$\mathcal{F}_{\text{rand}}$且在$\mathcal{F^2_\text{cr}}$混合模型下中止协议，那么协议中一定存在一方腐败。用反证法可以证明。

在恶意模型下，还需一个高效的三方抛硬币协议。定义功能函数$\mathcal{F_\text{coin}}$随机选择$s$个随机比特$v_1, \cdots, v_s \in {0, 1 }$，并把它发送给每一方。让各方调用$s$次$\mathcal{F_\text{rand}}$函数，然后公开结果。这里会存在一个问题，由于腐败方可能会公开错误的讯息，导致诚实方收到的结果不一致。故需要设计一个子程序$\mathsf{compareview}()$让$P_j$ 发送他的输出给$P_{j+1}$。若任意一方收到的结果不一致，协议终止。假设$P_i$是腐败方，那么$p_{i+2}$一定会收到正确的结果$v_1, \cdots, v_s$，因为他收到的公开值是由诚实方$p_{i+1}$发送的，不会受到腐败方的影响。

在秘密共享中，需要计算数组的随机排列，每个元素都是一组乘法三元组。令$\mathcal{F_\text{perm}}$是一个功能函数，输入从各方发送的长为$M$向量$d$，选择一个随机序列${1, \cdots, M }$上的$\pi$，返回一向量$d^\prime$，且$d^\prime = d[ \pi[i] ], i \in {1, \cdots, M }$。用Fisher-Yates shuffle算法来计算$\mathcal{F_\text{perm}}$，通过$\mathcal{F_\text{coin}}$获得随机性。

重构一方的秘密$\mathcal{F}_{\text{reconst}}$ 要重构秘密共享，就考虑输出中止的安全性。这个重构协议一则要保证只有一方收到输出，而且并不保证输出的安全性。如此这般，由接收方验证消息，要么共享一致则继续执行，要么中止协议。 协议中将$P_i$的共享发送给$\mathcal{S}$，启用模拟环境，他不会向任意方泄漏消息，若诚实方发送的共享不一致，腐败方就不会产生输出，协议中止。

三元组验证与发布 乘法三元组是具有$c = a \cdot b$特征的共享$([a], [b], [c])$。共享$[c]$是常数，若一方是恶意的，则可能是$c = ab \oplus 1$。下面协议证明三元组是重要的。这里$a, b, c$是公开的。 发布一组三元组和检查正确性，但这组三元组不可再用于协议中，这需要一个协议在不发布三元组的前提下验证三元组的一致性。给定$x, y, z$和$a, b, c$的共享，各方计算并共布$\rho = x \oplus a,\; \sigma = y \oplus b$，由于$a,\; b$是随机数，这些值并不会泄漏$x, \; y$。如果$(x, y, z)$和$(a, b, c)$中只有一个是正确的，另外一个是错误的，即$x \neq y \cdot z$但$c = a \cdot b$，那么$ z + c + \sigma \cdot a + \rho \cdot b + \rho \cdot \sigma = 1$。计算出这个值并发布出去，诚实方能发觉并中止协议。但这样会增大开销，若公开的值等于$0$，则必须$s_j= t_{j-1}$，每方只需要比较单个比特。

乘法三元组的生成 文中介绍安全生成三元组，一则要安全的生成三元组，二则要验证三元组的正确性。若是半诚实模型可以省去第二步。若诗恶意模型，如果敌手存在欺骗行为，则需要验证共享的$[c_i]$的一致性，但可能是$ c_i \equiv a_ib_i \oplus 1$而不是$c_i = a_ib_i$。用cut-and-choose检查三元组是否正确。两个三元组，一个用来验证其正确性，另一个用来检查是否泄漏了消息。其中只有一个验证不通过，诚实方就可察觉三方中存在腐败方。这需要把乘法三元组分成多组，利用之前的协议，在不泄漏第二组的前提下，利用第一组验证第二组的正确性。因此选择合适的分组的大小和发布三元组的数量，可以使得作弊的概率忽略不计。文中提出一个主张：令$N, B, C$有$N = CB^2,\; (B-1)\log_2C \leq \sigma$，生成乘法三元组协议在安全计算模型中止协议，统计误差为$ 2^\sigma $，并存在一个腐败方。

乘法三元组生产随机值，用$\mathcal{F}_{\text{rand}}$生成$[a_i],[b_i]$，由公开乘法三元组协议确保前$C$个三元组是正确的，$[a_i],[b_i],[c_i]$是连续的共享。若对于一批量中的三元组$([a_1],[b_1],[c_1])$是不正确的，那么会存在$j \in {2, \cdots, B }$中的三元组$([a_j],[b_j],[c_j])$一定是正确的，并且诚实方会中止协议。为了一次行产生大量的三元组，需要选择优化的参数¹。当错误三原则的概率为$1/2$时，敌手的欺骗概率最大为$2^\sigma$，此时$(\log_2N + 1)(B+1) \leq \sigma$。这表明$N = 2^{20}, \sigma = 40$，因为$(\log_2N + 1)(B+1) > 21 \cdot 2 > 40$，可以设置$B = 3$。为了使得三元组的概率更接近于$1/2$，设置$C = 3 \cdot 2^{20}$，这需要三原则的总数为$6 \cdot 2^{20}$。文献¹中对三元组进行了组合分析，固定$N = CB^2$，当$(B - 1)\log_2C \leq \sigma$，敌手欺骗的概率最多为$2^{-\sigma}$。为了尽量减少三元组的数量，$B$必须保持最小，设置$N = 2^{20}, \sigma = 40$，可以选择$B = 4, C = 2 ^ 16$。显然满足，总共需要三元组的数量为$NB + C = CB^3 + C = 2^{22} + 2^ {16}$，约为文献²的$2/3$。

参考文献

[1] Burra, Sai Sheshank, Enrique Larraia, Jesper Buus Nielsen, Peter Sebastian Nordholt, Claudio Orlandi, Emmanuela Orsini, Peter Scholl, and Nigel P. Smart. “High Performance Multi-Party Computation for Bi- nary Circuits Based on Oblivious Transfer” Journal of Cryptology 34, no. 3 (2021): 1-87.

[2] Nielsen, Jesper Buus, Peter Sebastian Nordholt, Claudio Orlandi, and Sai Sheshank Burra. “A New Approach to Practical Active-Secure Two-Party Computation” In Annual Cryptology Conference, pp. 681-700. Springer, Berlin, Heidelberg, 2012.