SPDZ 学习笔记-part1
概要
SPDZ主要包括两个阶段，离线阶段（预计算）主要基于同态加密生成在现阶段需要的参数，在线阶段主要基于秘密共享完成各种计算。 SPDZ可以计算有限域中的任何计算。 SPDZ 满足 UC 安全框架下的静态恶意敌手(static adaptive adversay)攻击模型，即 n 个参与方中，即使最多 n-1 个参与方恶意违反协议或者合谋。 SPDZ使用Message Authentication Code (MAC)，检测参与方是否诚实地进行计算，MAC参数在离线阶段生成。 SPDZ不检测哪个参与方为恶意参与方，在检测到协议被违反情况即停止协议运行而防止数据泄漏。
2
安全模型安全多方计算安全模型一般采用Universally composable（UC）模型[2]，按照攻击者能力可以划分为半诚实、恶意参与者，按照恶意参与者的门限可以划分为多数诚实、多数恶意协议。按照攻击者能力：
半诚实模型：各参与方在计算过程中完全遵从 MPC 协议，既不会违反协议篡改数据也不会多个参与方之间进行合谋。 恶意模型：攻击者允许随意篡改协议，可以联合他人进行合谋攻击。
多数诚实：恶意参与者不超过总参与方一半。 多数恶意：恶意参与者至多可以有个（总参与方为）。
3
基本定义
秘密分享值表示方法：共有两种表示方法,和，第一种主要用于表示输入的秘密分享值，第二种则主要用于表示全局密钥和随机数等参数。1.表示方法 有限域中的值的秘密分享值表示方法为：其中，，
各参与方持有,为公开值，为全局MAC密钥。
秘密分享值计算具有以下性质：其中，
2.表示方法
的秘密分享值表示方法为：
其中，，，各参与方持有
，为各参与方的密钥，主要验证MAC密钥和随
机数秘密分享值的MAC验证。
MAC密钥MAC密钥 全局MAC密钥秘密分享值表示方法为，由于每个参与方持有，因此各参与方可通过验证MAC密钥。为了打开，参与方将发送给，校验是否成立。三元组及乘法运算加法计算相对直接，直接利用秘密分享值的性质，计算加法，即可得到结果，。乘法计算需要借助三元组（Beaver Triple[3]），三元组在离线阶段生成，表示为,,，且满足，由于在实际生成三元组过程中可能会引入误差，因此，需要额外“消耗”(sacrificing)一组三元组,,，用于校验三元组。给定一组三元组,,，设输入为则乘法可按以下方法计算：首先打开得到，打开得到，然后计算。正确性验证：SPDZ协议
SPDZ协议主要包括离线阶段和在线阶段。
离线阶段
离线阶段需要用到同态加密技术，产生的辅助数据包括：
多元乘法三元组的秘密分享值；
随机数秘密分享值； 全局MAC密钥。
这些辅助信息和在线计算阶段的输入数据无关，因此可以提前进行计算。
以全局MAC密钥为例，介绍离线阶段生成参数过程：
1. 各参与方联合生成同态加密公钥和私钥，以 BGV 方案[4]为例，私钥和公钥具有线性特性，因此解密过程中各方可利用进行部分解密，然后把解密结果汇总得到最终明文结果，解密过程中不泄漏各自部分的私钥； 2. 各参与方生成随机数，然后利用进行同态加密得到密文(表示的同态密文)，并将密文发送给其他参与方; 3. 各参与方汇总得到，利用私钥进行联合解密，联合解密过程中会加入一个随机数进行混淆，然后reShare得到。离线阶段详细协议见下一part。
在现阶段
在现阶段主要完成计算以及中间值和结果的MAC校验等，基础计算主要包括加法、乘法等。在现阶段主要过程如下：
1. 初始化。准备全局MAC密钥，随机数秘密分享值，乘法三元组,,等参数。
2. 输入阶段。设参与方的输入为，向打开[r]，然后广播，各参与方计算。输入阶段主要是将输入值分片，产生对应的秘密分享值。
3. 加法计算。设输入为，计算。
4. 乘法计算。设输入为，则计算分为两步：1）使用三元组 校验,；2）计算。
5. 输出阶段。再输出最终结果前，需要对中间值、结果进行MAC校验，SPDZ 协议 MAC 验证时为了提高效率，可以在打开多个秘密分享值后通过一次MAC批量校验。
在线阶段详细协议见下一part。
参考文献
[1] I Damgård, Pastro V , Smart N , et al. Multiparty Computation from Somewhat Homomorphic Encryption[C]// Springer-Verlag New York, Inc. Springer-Verlag New York, Inc. 2012.
[2] R. Canetti, Y. Lindell, R. Ostrovsky, and A. Sahai. Universally composable two-party and multi-party secure computation. In STOC, pages 494–503, 2002.
[3] Beaver. Efficient multiparty protocols using circuit randomization. In J. Feigenbaum, editor, CRYPTO, volume 576 of Lecture Notes in Computer Science, pages 420–432. Springer, 1991.
[4] Z. Brakerski, C. Gentry, and V. Vaikuntanathan. (leveled) fully homomorphic encryption without bootstrapping. In ITCS, pages 309–325. ACM, 2012.
本文来自知乎作者：小明原文链接：https://zhuanlan.zhihu.com/p/533900089
往期推荐
横向联邦学习下隐私保护安全聚合：问题，方法，与展望
同态加密开源框架整理
为下一代可信计算设计更好的数据中心（arxiv）