如何计算秘密共享的数据

---

1. 加法秘密共享

假设 Alice，Bob，Charlie 分别拥有三个秘密值 $x_A, x_B, x_C$，我们在他们互相不知道对方秘密值的情况下计算出 $f(x_A, x_B, x_C) = x_A + x_B + x_C$。

首先 Alice 随机选取 $r_{AB}, r_{AC} \gets_R \mathbb{Z}_p$，则 $(x_A - r_{AB} -r_{AC}, r_{AB}, r_{AC})$ 记做 Alice 的加法秘密共享，简记为 $[x_A]$。

给定 $[x_A]$ 和 $[x_B]$，很容易计算 $[x_A + x_B] = [x_A] + [x_B]$

Note

$[x_A] = (x_{A,1}, x_{A,2}, x_{A,3})$

$[x_B]= (x_{B,1}, x_{B,2}, x_{B,3})$

$[x_A + x_B] = (x_{A,1} + x_{B,1}, x_{A,2} + x_{B,2}, x_{A,3} + x_{B,3})$

更一般地：

• Share addition: $[x_A + x_B] = [x_A] + [x_B]$
• Scalar multiplication: $[kx_A] = k\cdot [x_A]$
• Addition by constant: $[x_A + k] = (x_{A,1} + k, x_{A,2}, x_{A,3})$

尽管满足以上性质，但计算乘法依旧是个不小的挑战。如果我们有一个乘法三元组（Beaver multiplication triples），那事情就好办了。

假设每一方都有这样的秘密共享： $[a], [b], [c]$，其中 $c=ab\in \mathbb{Z}+p$

给定 $[x]$ 和 $[y]$ 之后，我们知道：

• 每一方都可以计算 $[x-a]$ 并公布他们关于 $x-a$ 的共享
• 每一方都可以计算 $[y-b]$ 并公布他们关于 $y-b$ 的共享
• 所有参与方都可以计算： $[z] = [c] + [x](y-b) + [y](x-a) - (x-a)(y-b)$

Note

$z= c+ x(y-b) + y(x-a) - (x-a)(y-b) = xy$

现在，我们可以在 $n$ 方之间计算任意的算术电路：

1. 各方进行秘密共享
2. 对于每一个加法计算，各方直接本地计算他们的共享
3. 对于每一个乘法计算，各方使用 Beaver 乘法三元组，注意，每次都需要使用不同的三元组
4. 各方公布结果的秘密共享，通过计算之后获得最终输出

如何获得 Beaver 三元组？

• 从信任第三方处获取，如 Intel SGX
• 使用不经意传输

比较：

	Secret-Sharing (GMW)	Yao
Type of computation	Arithmetic circuits ($\mathbb{F}_p$)	Boolean circuits
Number of parities	Aribitrary ($n$)	2
Round complexity	Depth of circuit	2
Communicaton	$\sim 2n\log p$ bits per multiplication gate*	$\sim 256$ bits per AND gate
Security	Information-theoretic (with Beaver triples)	Computational

*: can be improved farther

Read more:

lecture25 at virginia.edu

lecture7 at stanford.edu