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

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

图片来源于网络

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

我们从

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

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

两个方面进行了介绍。本期将主要围绕计算过程展开。

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

2. 计算过程

在算术电路模型和恶意敌手模型的情况下，安全多方计算可以简化成如下一个问题：假设和分别拥有两个秘密值（称为 secret），如何使得各参与者在不知道的情况下（除 了知道，知道）计算出和来？

1. 首先要让各参与方获得的相关信息，即如何泄露的部分信息给参与方。秘密共享（Secret Sharing）方案是解决这一问题的重要方法。从算术电路的特性来考虑，线性秘密共享是很好的考虑方式。一种最简单的方式，即，随机选取，使得，并让相应的参与方掌握，每个被称为参与者关于的share。这个过程可以通过如下实现：每个随机选取，并告诉，设置。可以注意到的是，这个随机选取的过程可以在计算之前通过预处理过程来提前完成，在计算过程只要将提前选取的随机数告诉数据拥有方即可。

2. 假设每个参与方已经秘密拥有和，并满足和。此时，需要考虑如何进行加法运算和乘法运算。

- 对于加法，有。因此，对于加法运算来说很简单，各参与方把自己拥有的秘密值和相加即可，即

而结果。

- 乘法的情况要稍微复杂一些。。为了保证安全，这将会涉及到公钥密码体制。因此，该步骤中计算量比较大。

采用随机化的思想来建立一个预处理过程可以减小这种计算量。假设存在随机值满足，设以及，那 么。因此，把和看做是常数，如果每个参与者掌握了满足，和，那么每个参与者只需要进行简单的线性计算

而结果。

可以看到的是，的值随机选择，和无关，可以通过预处理过程来提前建立。因此，问题变成了如何使参与方获得随机化 的，并满足条件。

在每个知道的情况下， 每个可以本地计算和广播和。当参与者收到所有的和后，相加即得和。

2.1 正确计算的保证

在运算的过程中，还需要考虑一个重要问题，如何得知参与者进行了正确计算，即如何保证计算并发布了正确的值。

图片来源于网络

由于秘密被线性分享，采用线性构造的消息认证码（Message Authentication Code，MAC）进行认证是正确选择。通过式1和2的计算方式，可以看到，MAC 也要求提供符合这两个式子的计算方式，即两个 MAC 值相加，MAC 值乘常数，MAC 值加常数。

图片来源于网络

减小数据量的一种有效方式是使用全局 MAC 方案，即使用同一个密钥对 secret 进行 认证。毫无疑问，这违背了 one-time 的使用原则，线性构造的 MAC 将不再安全。解决这个问题的一种平常方法是构造-time 的 MAC。另外一种考虑就是将认证密钥和认证码分散，计算完毕后，组合出密钥和认证码来验证。

因为认证码和密钥的分散，MAC 的构造可以简化成。同时需要满足 MAC 可加常数的计算需要，最终的 MAC 构造 为，其中为常数（可取零）。密钥可以定义为，其中为参与者选取的随机数。因此，也需要被认证。该认证通过持有密钥，的方式来认证。同时，这个认证结果也需要分散，分散的过程类似于对 share 的分散。

未完待续......

▿点击阅读原文查看往期精彩