诚实大多数下抵抗恶意敌手的高效安全三方计算
ABSTRACT
本文提出一个新的恶意安全下诚实多数的关于任意函数的安全三方计算协议。该工作基于Araki 等人（CCS'2016）提出的半诚实协议，改进为恶意敌手、诚实大多数模型下的Correct with Abort 安全三方计算协议。主要是通过构造Beaver乘法元组来对门电路进行验证，从而达到计算正确的目的。不同于TinyOT和SPDZ，本文基于cut-and-choose范式来保证元组被正确构造，同时提出新的可被用在相关cut-and-choose的组合分析方法。论文原文链接如下：
https://link.springer.com/chapter/10.1007/978-3-319-56614-6_8
INTRODUCTION
安全计算的设定中，要求一组互不信任的多方联合计算一个约定的函数得到输出，而不泄漏关于输入的任意信息。安全计算协议要求保证1）Privacy；2）Correctness。为刻画安全性，对敌手的行为分为半诚实和恶意两种，对敌手的数量分为诚实多数和恶意多数两种。尽管前人已有工作做到使协议满足计算安全性或者统计安全性。但是这些在半诚实或者恶意的设定下要做到统计安全性要求诚实者的数量不少于2/3。
通常有两种方法来构造通用安全计算协议的方法：
1）基于Secret-Sharing，优点是适用于低带宽，通信量少，但是交互多。
2）基于Garbled-Circuits的方法，优点是常数轮交互，适用于高延迟网络的场景，但是混乱电路带来巨大的通信开销。
本文关注在恶意安全下诚实多数的三方计算，期望在一个高速的网络环境下实现高通量（适用于一个网络设备较好的场景下，计算效率高，吞吐量大）。Araki 等人提出的半诚实协议能实现每秒70亿的AND门计算。我们的方法满足恶意安全性，在同样的实验设定下性能上可以达到50亿的门电路计算。
Outline of Solution
首先提出2-out-of-3的秘密分享方案以及一些重要的性质。
描述半诚实下的乘法（AND）协议，并且证明本文依赖的重要性质：
对于任意恶意敌手，乘法协议计算后，诚实方总是有一个有效的秘密份额。
这个值要么等于输入的AND（半诚实），要么等于它的补（恶意）。
介绍如何生成关联随机性（correlated randomness，）。
使用以安全的方式生成，它给所以参与方提供随机份额。
一个非常重要的性质是是非交互的，所以也是非交互的。
这意味着可以借助以满足恶意安全的方式生成乘法元组中的随机分享。
接着可以利用生成安全抛硬币（互不信任的多方生成一个随机bit的方法）。
其实用生成随机数后，我们需要交互才能公开一个数，如何保证交互的过程中保证恶意安全性？
这一节将讲这一个问题。
接下的部分会讲额外的Functionalities。
做cut-and-choose的时候需要用于随机排列（random permutation，）。
另外我们需要定义恶意安全下的shares（）和open shares（）。
接下来介绍这些子协议之间的关系，
特别说明：本文工作仅适用于3方的情况，且仅仅是恶意安全下诚实多数情况的Correct with Abort。没有实现Fairness.
BUILDING BLOCKS AND SUBPROTOCOLS
The Secret Sharing Scheme
定义2-out-of-3分享：为了分享一个比特 那么约定
的分享是，这里 的分享是，这里 的分享是，这里
可以看到任意的一方是无法知道原始值的，且任意的两方是可以还原的，比如给定，。
Claim 1：当一方的秘密份额确定了，那么另外两方的份额也被确定.
定义Opening shares：的秘密分享为，那么每一方发送给，并且每一方计算。表示为
Local operators for shares：
Addition ：每一方，假定是的秘密分享，是的秘密分享。那么每一方对应计算 Multiplication by a scalar ：每一方计算 Addition of a scalar ：每一方计算 Complement ：每一方计算
Claim 2：令表示的秘密分享，令表示一个离散值。那么有下面的式子成立：
一致性（Consistency）：一致性相对于诚实方来说的，在恶意者存在的情况下，在交互中它的行为是任意的，可以发送任意的数字使得诚实方得不到任意值的正确秘密分享。假设是恶意方，当在Opening shares的时候，对于有，对于对于有。由于是恶意的，则中的有可能是被篡改过的。另一方面，如果是正确的，那么有。所以做一个代换：
在诚实多数的约定下，和是诚实的，下面定义consistency
Definition 1：令分别持有。令为恶意方，如果成立，那么我们说shares是consistent的。
Computing AND Gates -- One Semi-Honest Corrupted Party
乘法（AND）的计算分为两阶段，假设是的分享，是的分享，其中。计算
Step1 -- 计算-sharing 的计算，发送给 的计算，发送给 的计算，发送给 Step2 -- 计算-sharing。这一步是为了保持形式的一致，另外计算都发生在本地 存储，其中 存储，其中 存储，其中
Lemma 1：如果是consistent的，并且是上述乘法协议在一个恶意者存在的情况下关于的结果，那么要么是的一致性分享，要么是的一致性分享。
Proof：如果恶意方遵从协议的执行，那么是的一致性分享。不失一般性，假设为恶意者，它唯一可以偏离协议规则的方式是将原本发送的改为发送。的。不会受到影响，根据Consistent的定义，。此外，它也是的分享，因为。
Generating Correlated Randomness --
协议强依赖于随机有关联的bits。因此定义两种类型的correlated randomness。
Type 1：考虑一个理想的方法，它可以随机的选择满足，并且发送给。 Type 2：考虑一个理想的方法，同样可以随机的选择，然后将发送给，类推。
Proposition 1：如果是伪随机函数，那么协议2.5满足诚实多数下的恶意安全
Generating Shares of a Random Value --
描述如何生成一个随机数的sharing，满足各个参与方对其真实值未知。
观察到。可以定义
Proposition 2： 协议2.9满足诚实多数下的恶意安全
Coin Tossing --
现在提出一种高效的三方抛硬币协议，它在存在一个恶意者的情况下也是安全的。想法是调用生成随机数的秘密分享，然后open这个结果得到随机数。但是这是有问题的，因为在恶意者而在的情况下，有可能在open的时候会发送不正确的值导致无法成功还原。一个解决办法就是各个参与方将还原的互相比较。如果一致则接受它，如果不一致则输出Abort。
Proposition 3： 协议2.11满足诚实多数下的恶意安全
Random Shuffle --
作为一个辅助协议，需要计算一个array的随机排列
Proposition 4： 协议2.13满足诚实多数下的恶意安全
Reconstruct a Secret to One of the Parties --
下面展示以一种安全的方式打开一致性为。区别于前面提到的 open procedure有两点不同：1）仅仅是一方得到输出；2）这个open procedure不保证正确性（correctness）。这里的Reconstruct保证一方要么得到正确的输出要么得到Abort。
Robust Sharing of a Secret --
作为一个子协议被用来将参与者的输入进行秘密分享。
Triple Verification With Opening
在主协议中，参与方采用两阶段的方法生成乘法元组：
Step 1：参与方两次调用生成随机数的秘密分享 Step 2：参与方调用半诚实乘法协议计算
元组使用打开验证正确性基于一个事实：如果shares是一致性的，并且，那么诚实方之一一定能检测出来的。这个协议之所以with opening是因为被揭露了。
Triple Verification Using Another (Without Opening)
通过打开验证的方式会使得被披露导致不再可用。这一节介绍不使用Opening的方式验证乘法的正确性。主要的想法是。给定和。参与者打开和（没有泄露的值，因为是随机的）下面会证明，如果，中之一是正确的，另一个不是正确的（比如，但是），那么有。因此可以通过披露这个值来进行验证。
Lemma 1：如果是一个正确的乘法元组并且 是一致性的分享，但是不是乘法元组。那么协议2.24中所有的诚实方会输出Abort。
Proof：令是恶意方，有但是。如果那么有。根据和的定义有
Proof：令是恶意方，有但是。如果那么有。根据和的定义有
SECURE GENERATION OF MULTIPLICATION TRIPLES --
我们使用三方协议生成正确的乘法元组。主要想法是参与方使用生成许多，然后使用半诚实的乘法协议计算。为了满足恶意安全性，我们使用cut-and-choose来检测这些元组的正确性。
SECURE COMPUTATION OF ANY FUNCTIONALITY
这一小节说明如何利用前面介绍的子协议计算任意函数。
EFFICIENCY AND COMPARISON
本文与P. Mohassel et al.提出的方法（CCS‘15）进行了比较
Future Work
除了隐私保护，安全多方计算还能保证正确定、公平性和输出可达性。目前在隐私保护机器学习和安全多方计算结合的领域，业界最新的方案已经做到了诚实大多数下的输出可达性，一般是五方或者四方下的。而本次介绍的论文则是后续方案的基础部分。本专栏计划后续将逐步介绍该部分工作。
本文与李开运 @李开运 合作完成。
作者简介：
董业， 本科毕业于山东大学计算机科学与技术专业，目前在中国科学院信息工程研究所攻读博士学位。主要研究兴趣包括隐私保护、安全多方计算、同态加密和机器学习。知乎：酸菜鱼。
往期内容：
Mike Rosulek 课程系列(三): 不经意传输及其优化
Fantastic Four: 具有恶意安全的诚实大多数四方安全计算
欢迎投稿
邮箱：kedakeyin@openmpc.com
参与更多讨论，请添加小编微信加入交流群