Kun Liu

Kun Liu

CS & Applied Math & MPC @ GZU | Phd

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

1 minute read

Published:

安全三方计算

在ABY3和Falcon等一些方案中，都用到了三方安全计算技术。这些方案中零共享、(3,3)门限共享和(3, 2)门限共享等都来源于CCS2017的一篇关于三方计算的文章，High-Throughput Secure Three-Party Computation for Malicious Adversaries and an Honest Majority。文中称设计的协议满足任何计算功能的安全三方计算协议，其安全性满足半诚实模型，两方诚实和一方恶意敌手的模型。协议在计算上和信息论上通信复杂度和计算复杂度都低。构造协议首先构造乘法三元组，然后用三元组验证电路门计算是否正确。和SPDZ协议一样，本文也是采用切割和选择(cut-and-choose)范式验证三元组构造的正确性。参与方秘密输入希望联合计算输入，除了输出相互之间不泄漏任何输入信息。安全协议必须保证隐私性和计算结果正确性。通常安全性由敌手的行为定义。半诚实模型定义敌手执行协议但试图从协议中推测出秘密信息，恶意模型定义敌手能力是运行任意多项式时间的攻击策略。在信息论模型中，即使存在无限计算能力的敌手，也会无条件安全。相比之下，存在一个多项式时间的敌手更满足密码学难题假设。构建安全计算协议一般用两种方法

  • Secret Sharing 通过各方对电路的每个门进行交互操作
  • Garbled Circuit 通过各方构建加密的电路工作

两种方法各有优点，GC生成的协议通信轮次是恒定的，通信轮次和电路深度呈线性关系；SS的相比GC带宽较低，可以在低通信条件下实现大的吞吐量。

秘密共享方案 定义(3,2)秘密共享方案，共享一个比特$v$，处理者选择三个随机比特$s_1, s_2, s_3 \in {0,1 }$，限制$s_1 \oplus s_2 \oplus s_3 = v $

  • $P_1$的共享是一对$(t_1, s_1),\; t_1 = s_3 \oplus s_1$
  • $P_2$的共享是一对$(t_2, s_2),\; t_2 = s_1 \oplus s_2$
  • $P_3$的共享是一对$(t_3, s_3),\; t_3 = s_2 \oplus s_3$

显然三方的共享都不会泄露秘密$v$，但是任意两方能够得到$v$。若任意得到两方共享，可以计算$ v = t_1 \oplus s_2 = t_2 \oplus s_1 = t_3 \oplus s_1$。

  • 定义子协议$ \mathsf{open}([v]) $，$v$是秘密共享，对$P_i$ 发送$t_i $给$ P_{i+1} $，并在本地计算$ v = s_i \oplus t_{i-1} $
  • 对共享的本地操作算子:
    • 加法$ [v_1] \oplus [v_2]$: 给定$v_1$的共享$(t^1_i, s^1_i)$和$v_2$的共享$(t^2_i, s^2_i)$，计算得$(t^1_i \oplus t^2_i, s^1_i \oplus s^2_i)$
    • 标量乘法$ \sigma \cdot [v] $：给定$v$的共享$(t_i, s_i)$和值$ \sigma \in {0, 1 }$，计算$( \sigma \cdot t_i, \sigma \cdot s_i)$
    • 标量加法$ [v] \oplus \sigma $：给定$v$的共享$(t_i, s_i)$和值$ \sigma \in {0, 1 }$，计算$( t_i, s_i \oplus \sigma )$
    • $ \overline{[v]} $的补：给定$v$的共享$(t_i, s_i)$，计算$\overline{[v]} = (t_i, \overline{s_i})$

计算$\text{AND}$门

此协议分两个阶段：一是各方计算计算一个比特的$\text{AND}$门的$(3,3)\mathsf{XOR}$共享；二是将上面的$(3,3)\mathsf{XOR}$共享转换成$(3,2)\mathsf{XOR}$共享。令$v_1$的秘密共享是$(t_1, s_1), (t_2, s_2), (t_3, s_3)$，$v_2$的秘密共享是$ (u_1, w_1), (u_2, w_2), (u_3, w_3) $，并假设三方有相关随机数$\alpha_1, \alpha_2, \alpha_3 $，使得$\alpha_1 \oplus \alpha_2 \oplus \alpha_3 =0 $，计算$v_1v_2= v_1 \land v_2 $的$(3,2)$共享：

  • 各方同时计算$(3,3)$共享：
    • $P_1$计算$r_1 = t_1 u_1 \oplus s_1 w_1 \oplus \alpha_1$，发送$r_1$给$P_2$。
    • $P_2$计算$r_2 = t_2 u_2 \oplus s_2 w_2 \oplus \alpha_2$，发送$r_2$给$P_3$。
    • $P_3$计算$r_3 = t_3 u_3 \oplus s_3 w_3 \oplus \alpha_3$，发送$r_3$给$P_1$。
  • 计算$(3,2)$共享，各方用给定的$(3,3)$共享和前一步信息在本地计算构造$(3,2)$共享
    • $P_1$存储$(e_1, f_1)$，这里$e_1 = r_1 \oplus r_3, \; f_1 = r_1$
    • $P_2$存储$(e_2, f_2)$，这里$e_2 = r_2 \oplus r_1, \; f_2 = r_2$
    • $P_3$存储$(e_3, f_3)$，这里$e_3 = r_3 \oplus r_2, \; f_3 = r_3$

显然有$ f_1 \oplus f_2 \oplus f_3 = r_1 \oplus r_2 \oplus r_3 = v_1 v_2 $，可以看到即使存在一方是恶意的情况，共享的一致性也能保证。

相关随机性

三方安全协议的安全性强烈依赖使用的相关随机比特，(3,3)共享和(3,2)共享拥有不同的相关随机性

  • (3,3)共享中理想函数$\mathcal{F^1_\text{cr}}$随机选择，把$\alpha_i$ 发送给$P_i$，并使得$\alpha_1 \oplus \alpha_2 \oplus \alpha_3 = 0$
  • (3,2)共享中理想函数 随机选择 ，把$( \alpha_i, \alpha_{i+1})$发送给$P_i$

有效生成相关随机性，若要生成(3,3)共享相关随机性，让$P_j$选择随机比特，并发送给$P_{j+1}$。$P_j$定义，显然$\alpha_i$具有零共享，$ \rho_j$出现两次。计算$(3,2)$共享的相关随机性，各方$P_j$发送一个随机数$\rho_j$，各方$P_j$输出一对$(\rho_{j-1}, \rho_j)$。每通信一轮，发送一个比特，但实际用门的通信良会增加一倍，这会影响效率。下面是安全计算相关随机性的协议，中间不存在各方之间的交互。当输出时，$\alpha_1 \oplus \alpha_2 \oplus \alpha_3 = 0$，对于每一方$P_j$不会知道用于生成$\alpha_{j+1}$和$\alpha_{j+2}$的$k_{j+1}$。因此，$\alpha_2 \oplus \alpha_3 = \alpha_1$，$\alpha_{j+1}$和$\alpha_{j+2}$对于$P_j$是伪随机的。

定义理想函数

三方安全协议理想功能是随机选择$\alpha_1, \alpha_2, \alpha_3 $并将$\alpha_j$发给$ P_j $，但是要实现这样的功能需要一个完整的抛硬币协议。为了让模型中达到非交互性，要选择恶意一方$P_i$有选择$k_i$，这种情况表现在用一个具体的伪随机函数生成。假设使协议更加真实，定义函数用来生成腐败一方的值。腐败方用伪随机函数选择两个密钥$k, k^\prime$，并作为函数的输入。密钥用来生成腐败方生产的数值，$\kappa$表示密钥的长度。若$F$是一个伪随机函数，则下面协议能分别安全计算，只要存在一方是恶意的，协议自动中止。原文中给定了一个敌手和一个模拟器，利用模拟器的伪随机函数生成的$k,k^\prime$和敌手构建的密钥计算上不可区分，证明协议的安全性。

You May Also Enjoy