读懂这篇，全面理解安全多方计算

上一期我们介绍了“安全多方计算”的计算过程，安全多方计算是由图灵奖获得者姚期智先生通过百万富翁问题引出的一个数据隐私保护方面的重要领域。

图片来源于网络

姚氏百万问题可表述为：Alice 和 Bob 是两个百万富翁，他们想知道谁更富有，但他们都又不想把关于自己财富的任何信息透露给对方。在这样一种情况下，双方都不想透露自己真实信息，比较两个人的财富多少，并给出可信证明。

我们在以往两期视点中，已经讲解了

1.1 安全模型（恶意敌手模型）

1.2 电路选择（布尔电路和算术电路）

2. 计算过程

2.1 计算过程的保证

四个要点。本期将主要围绕预处理过程和采用 Obvious Transfer 协议进行预计算来程展开。

往期回顾 ? 在充分保护隐私的前提下，如何知道两位“马爸爸”谁更富有？

? 在无从知道“秘密值”的前提下，如何实现“秘密计算”？

3. 预处理过程

预处理过程解决的问题是如何使参与方获得随机化的

(a_i,b_i,c_i)

（称为三元组）等，并满足条件

\sum a_i\times \sum b_i=\sum c_i

。当然，每个三元组都是需要经过 MAC 认证的。

设，和。在三元组

(a_i,b_i,c_i)

的构造中，

P_i

可以随机选择

a_i

和

b_i

，然后来构造

c_i

。可以看到，

c=ab=\sum a_i\times \sum b_i =\sum (a_i\sum b_j)

。

c=ab

的正确性通过“sacrifice”技术来验证，即产生另外一对三元组

(\tilde{a},\tilde{b}, \tilde{c}=\tilde{a}\tilde{b})

，并用该三元组来验证

(a,b,c)

的正确性，即利用

c=ab=[\tilde{a}+(a-\tilde{a})][\tilde{b}+(b-\tilde{b})]

来验证。

整体考虑

c=ab

。假设

是支持一次乘同态多次加同态的密码方案。参与者

P_i

公开

E_i(a_i)

和

E_i(b_i)

，并进行如下操作：

计算：。
利用分散：
- 每个随机选择，设，那么可以设；
- 解密得到，并设，其余参与者设，。

在这过程中，使用零知识证明来保证

P_i

知道相应明文。

4. 采用 OT 方式

采用 Obvious Transfer（OT）协议也可以来进行预计算。在一个1-out-of-2 OT 协议中，发送者输入消息

s_0,s_1

并得不到任何输出，接收者输入一比特

k \in\{0,1\}

并得到输出

s_k

。而在一个 ROT 协议中，发送者不输入任何消息，得到两个随机消息

s_0,s_1

，接收者输入一比特

b\in \{0,1\}

并得到输出

s_k

。

图片来源于网络

现在，

P_i

拥有

，

P_j

拥有

，假设

有

比特，可以通过进行

次 OT 协议来计算

。在第

次 OT 协议中，

P_i

随机选取

s_l

，输入

s_l

和

s_l+a

，

P_j

每次输入

的第

比特

b_l

，得到

q_l=s_l+b_la

。可以看到，

\sum^{k-1}_{l=0}(q_l2^l)=\sum^{k-1}_{l=0}(s_l2^l)+a\sum^{k-1}_{l=0}(b_l2^l)=\sum^{k-1}_{l=0}(s_l2^l)+ab

。设

q=\sum^{k-1}_{l=0}(q_l2^l),s=-\sum^{k-1}_{l=0}(s_l2^l)

，则

P_i

和

P_j

分别得到了

和

，满足

q+s=ab

。

这个方法需要在计算过程中每次都使用 OT。可以提前利用 OT 分别得到和，计算时发送给，利用和其相乘来得到同样结果。如果固定（在 MPC 中，考虑认证码的生成，始终用密钥分量参与运算），可以使用伪随机函数 PRF 作用在和上，即，其中为递增量，得到类似于多个 OT 的输出。另外，可以利用 ROT 来为选择随机值，而不是让选择随机值。

图片来源于网络

这个方法需要在计算过程中每次都使用 OT。

P_i,P_j

可以提前利用OT分别得到

\{s_{i,0},s_{i,1}\}

和

\{s_{i, b_i}\}

，计算时

P_i

发送

\{s_{i,0}-s_{i,1}+a\}

给

P_j

，

P_j

利用

b_i

和其相乘来得到同样结果。如果

P_j

固定

（在 MPC 中，考虑认证码的生成，

P_j

始终用密钥分量

\alpha_j

参与运算），可以使用伪随机函数 PRF 作用在

\{s_{i,0},s_{i,1}\}

和

\{s_{i, b_i}\}

上，即

t=PRF(s,j)

，其中

为递增量，得到类似于多个 OT 的输出。另外，可以利用 ROT 来为

P_i

选择随机值，而不是让

P_i

选择随机值。

考虑认证码的情况，

\alpha:=(\alpha_1,\ldots,\alpha_n)

，

x:=(x_1,\ldots,x_n)

，要使得每个参与者

P_i

掌握

\alpha x

的 share，那么

\alpha_i x_j

的计算都可以通过上述方法实现。假定每个参与者

P_i

拥有秘密为

a_1,a_2,...

，在认证码的计算过程中，

P_i

加入随机量

a_0

（起到随机化的作用）同样参与认证，即每个参与者也拥有

\alpha x_o

的分量。在认证码生成好后，形成

a_0,a_1,a_2,...

的随机线性组合以及相关认证码同样的线性组合来一次性确定关于

a_1,a_2,...

的认证码是否正确生成。

设

\vec{a}

是个

\tau

维向量。在三元组生成过程中可以为每个参与者生成满足

\vec{a}b=\vec{c}

的

(\vec{a},b,\vec{c})

的分量

\vec{a_i}=(a_{1i},a_{2i},...),b_i,\vec{c}_i=(c_{1i},c_{2i},...)

。然后选取随机向量

\vec{r}

和

\vec{\tilde{r}}

，计算内积

a_i=<\vec{a_i},\vec{r}>

，

c_i=<\vec{c_i},\vec{r}>

，以及

\tilde{a}_i=<\vec{a_i},\vec{\tilde{r}}>

，

\tilde{c}_i=<\vec{c_i},\vec{\tilde{r}}>

，即每个参与者掌握

(a,b,c=ab)

和

(\tilde{a},b,c=\tilde{a}b)

的分量。这种做法主要从

a,b,c

的隐私上考虑。最后，利用“scarifice”技术验证正确性，选取一随机数

，利用

sc-\tilde{c}=b(sa-\tilde{a})

验证

c=ab

的验证性。这种做法的安全性可以用 leftover hash lemma 来保证。

5. 结语

我们以 SPDZ 方案简单介绍了一下一类安全多方计算协议的原理。区块链也是一个无信任中心的系统，两者在技术特点上有一些可类比性，也都有一些自己独特的性质。数据作为一种重要的生产要素，可以利用区块链和安全多方计算等技术的结合，促进其能安全地流转和交换，并保证其中的安全和隐私性，对实际业务带来重要支撑。

▿点击阅读原文了解更多