Latincrypt'21: 最小化在线通信量的具有中止的诚实大多数MPC

根据所需的安全级别和对计算输出所需的保证, MPC协议通常涉及如下几个要点:

• 诚实大多数(honest-majority): , 不依赖于任何计算困难性假设, 可做到信息论安全, 计算效率高;
• 不诚实大多数(dishonest-majority): , 必须依赖于计算困难性假设, 只能做到可证明安全, 计算效率低.

• 被动腐化(passive corruption): 遵循协议, 但试图从发送/接收的信息中获得有用的信息;
• 主动腐化(active corruption): 敌手可以任意地偏离协议.

• 输出可达性(guaranteed output delivery): 无论敌手行为如何, 诚实方必须得到输出;
• 公平性(fairness): 如果敌手得到了输出, 则诚实方也必须得到输出;
• 中止安全性(Security with abort): 敌手可以控制哪些诚实方能得到输出, 哪些诚实方中止. 即诚实参与方要么得到正确的输出, 要么中止协议(得不到输出).

Preliminaries

3.1 Notation and Security Definition

方, 腐化门限, 诚实大多数设定, 满足. 是组成或的环, 为素数, 为非负整数. 是统计安全参数.

假设点对点安全信道的同步网络、广播信道.

假设存在一个带有中止(abort)的广播信道, 即各参与方要么得到广播的值, 要么生成并中止. 此外, 还假设当诚实方中止时, 所有诚实方均中止. 可通过echo-broadcast来实例化, 即让发送方通过点对点信道发送要广播的值, 然后接收方交换值的hash, 若不一致则中止.

3.2 Linear Secret-Sharing

考虑上的线性秘密共享方案(linear secret-sharing scheme, LSSS), 记为, 包含随机映射函数: , 使得对所有, , 满足如下三点:

• 隐私性(Privacy): 对于满足的任意子集, 不能从中得到的信息.
• 重构(Reconstuction): 存在, 使得对满足的任意子集, 有.
• 线性性(Linearity): 给定, 的像在中.

记, .

的定义可以扩展到多于个份额: 令满足, 对于满足的所有,

• 若, 则称份额是一致的(consistent).

• 若, 则称份额是不一致的(inconsistent)/无效的(invalid).

在诚实大多数秘密共享方案中, 若份额是一致的, 则重构的值必然是正确的. 换而言之, 如果敌手修改了中腐化方的个份额, 但是, 则必有.

3.3 Reconstruction Protocols

本文涉及两种重构打开(opening)协议:

• Robust opening: 打开时所有参与方都需要发送其份额给打开方, 被打开的值一定是正确的;
• Non-robust opening / Loose opening: 打开时只有个参与方发送其份额给打开方, 被打开的值可能是不正确的().

两种打开协议的具体过程如下:

Loose opening依赖于诚实大多数的性质, 通信量可进一步优化为让个参与方发送其份额给某个特定的参与方king, 如, 由使用这些份额进行重构并向所有参与方广播结果, 如此总通信量为个环元素(点对点信道传输个, 广播信道传输个).

但是, 如此做恶意的可能会广播错误的结果, 解决方案是选择其他参与方作为king, 使用线性纠错码, 先将要打开的秘密序列批处理为一个向量, 并使用线性纠错码对该向量进行编码, 然后码字中的每个秘密都由不同的特定参与方打开, 最后对得到的码字进行纠错或检验.

3.4 Sampling Shares of Random Values

本文中应用了如下两个功能来选取秘密共享的随机数:

3.5 Correct Multiplication

预处理阶段所使用的功能: 取随机数份额和为输入, 返回. 做法如下:

1. 运行被动安全的协议, 返回结果为, 其中为主动敌手发起附加攻击引入的附加错误值(additive error);
2. 验证.

若为有限域, 则可以使用"sacrifice"技术[2], 即通过牺牲另一个满足的随机乘法元组, 来验证的一致性(consistency). 如此每个乘法需要打开一个值用于检验, 因此通信量与需要检验的元组数量相关. 为了同时对个乘法元组进行检验, 目前最高效的方案是使用GS20基于多项式插值和域的性质的方案[3], 其通信量与无关.

Optimizing the Online Phase

4.1 Masked Secret Sharing

本文使用如下线性秘密共享方案:

• : 选取随机茫化, 调用并计算作为份额的一部分, 即;
• : 调用, 若, 则输出, 否则输出.

很容易验证该方案的加法同态性.

4.2 General Overview

利用诚实大多数LSSS的关键性质: 重构要么得到正确的值, 要么生成中止信号, 可以构造如下高效的具有中止安全性的主动安全的MPC协议:

容易验证上述协议满足中止安全性.

本文目标在于尽可能地优化在线阶段的开销, 将在线阶段的三元组一致性检验所需开销转移到预处理阶段, 因此预处理阶段的效率可能比其他方案低, 总的来说, 本文对上述协议提出了如下两个优化:

1. 用秘密共享方案替代秘密共享方案, 乘法门计算的在线阶段只需打开一次, 而后者需要打开两次;
2. 用Loose opening 替代Robust opening , 在线阶段只有参与计算, 在最终输出前取所有打开值的随机线性组合, 并Robust opening其结果进行验证, 此时所有参与方(包括)都需要参与验证.

优化1仅优化了在线阶段的通信量. 优化2中除了优化通信量外, 还节省了计算资源.

4.3 Main Protocol

取为有限域. 按照上述两个优化思想, 本文给出的优化协议如下:

很容易验证方案的正确性, 而隐私性则基于一次一密, 下面表明验证(check)阶段进行的验证有极大概率是正确的.

令表示在计算阶段中通过loose opening打开的值的份额. 设, 其中为敌手引入的附加错误值. 在验证阶段, 参与方打开的值为:

只需验证. 以极大概率成立, 当且仅当对于所有, 都有. 若存在, 但敌手作恶后仍能通过验证, 则有, 由于每个都是在敌手引入之后在上均匀随机选取的, 故这种情况发生的概率仅为, 于是敌手作恶成功的概率可忽略不计.

通信复杂度: 预处理阶段生成三元组的通信开销与参与方数量线性相关. 在线阶段忽略验证阶段和调用的开销, 则每个乘法门总通信开销来自于调用一次的开销, 为个元素, 故使用优化后总通信量为个元素.

Removing the Extra Parties 

在上一节的协议中, 在线阶段大部分都由个参与方完成, 而剩下方仅在预处理阶段和输出阶段参与计算, 因此在线阶段这个参与方可以离线. 下面考虑进一步优化为输出阶段仅由个参与方完成, 如此预处理阶段结束后剩下方可以永久离线. 仍然考虑.

5.1 General Overview

主要想法是让方参与离线阶段生成必要的乘法三元组外, 还需生成MAC, 在线阶段只需要方参与计算并用MAC来确保正确性. 回顾上一节中的协议, 在线阶段可以仅由方运行, 因为在完成预处理后, 在线阶段只需要进行opening. 然而, 由于秘密共享方案的门限是, 方不能提供足够的冗余, 使得主动敌手可以发起附加攻击修改公开值.

为了解决这个问题, 与前一节的方法类似, 令是打开后结果为的份额.

1. 各参与方选取随机公开值, 令, ;
2. 所有方打开来检验的打开值是否为, 以保证值的正确性.

与上一节的不同之处在于, 此时不用额外的方以robust opening的方式打开. 但是, 只有方并不能保证打开的值是一致的, 为了解决这个问题, 使用不诚实大多数MPC协议Turbospeedz中的一个技术[4], 不将秘密共享为, 而是秘密共享为, 其中是全局随机密钥MAC, 也被秘密共享为, 在整个计算中, 保持不变.

因为是隐藏的, 且是线性的, 可以确保正确性, 但是仍需保证敌手在check阶段中引入的误差与诚实方的份额无关. 为此, 使用"commit-and-open"方法. 为了打开, 每个首先使用理想的承诺功能承诺他们的份额, 然后再调用将收到的份额与承诺的份额进行一致性检验. 尽管敌手仍能使揭示的值为错误的, 但是由此引入的误差与诚实方份额无关. commit-and-open只在协议的检验阶段和输出阶段中需要, 计算阶段只需调用.

仍然可以通过随机线性组合的方式一次性验证多个值的正确性而不需要额外的个参与方. 设方运行在线阶段得到的打开后的结果为. 通过使用额外的份额, 进行如下验证:

1. 选取随机公开值, 令, , ;
2. 各参与方通过loose opening打开, 若结果不为, 则中止协议.

敌手作恶但检验能通过当且仅当, 概率至多为, 此时至少存在一个, 使得, 当足够大时, 该概率可以忽略.

5.2 Full Protocol Description

完整的优化协议如下:

通信复杂度: 在线阶段, 不考虑最终验证时, 每个乘法门需要通信个元素, 由于只在上进行广播, 因此, 于是每个乘法门需要通信个元素.

Evaluation

本节考虑把[Main Protocol]中的方案扩展到环, 此时需要解决如下两个问题:

1. 在上的实例化;
2. 由于上存在零因子, 最后的检查阶段中验证的, 恶意敌手能以的不可忽略概率通过检验.

下面分别进行讨论.

6.1 Checking Multiplications over

设是通过被动安全协议生成的乘法三元组集合, 其中, 是敌手引入的附加错误值. 目标是对于所有, 验证. 首先回顾[5]中在上的检验方法, 然后再将其扩展到上.

6.1.1 Checking Triples over

设, 假设检验中包含的三元组之一是随机且未被使用的. 检验过程[5]如下:

1. 寻找, 使得对任意, 是可逆的(非零元). 这样的序列是存在的, 因为;
2. 令和是上次数至多为的多项式, 对于, 满足和, 对于, 令, . 对于, 各参与方使用拉格朗日系数从和中本地计算和;
3. 对于, 使用抵抗附加攻击的乘法协议计算;
4. 各参与方调用, 得到;
5. 令是次数至多为的多项式, 对于, 满足. 各参与方使用拉格朗日系数从中本地计算;
6. 各参与方使用拉格朗日系数从中本地计算, 从中本地计算;
7. 各参与方打开, 和, 验证.

首先, 最后一步中打开的值不会破坏协议的隐私性, 因为这些份额是原始三元组的线性组合, 其中有一个是随机且未被打开的.

接下来说明, 对于, 协议正确地检验了. 事实上, 若存在, 则作为多项式, 根据代数基本代理, 除了至多的概率外, 有.

6.1.2 Extending the check to

上述方案不能扩展到上, 原因如下:

1. 由于零因子的存在, 不可能对所需次数的多项式进行插值;
2. 即使可能, 对于两个不相等的多项式, 对随机点的求值能得到相同结果的概率很小.

为了解决这些问题, 引入Galois扩环(Galois ring extension) [6]. 令表示上次数为的首一多项式, 使其模2在上是不可约的. 称商环是次数为的Galois环. 与扩域类似, 中的元素可以看出是次数小于的多项式. 我们将视为次数为0的多项式, 嵌入中. 这些环有如下性质[6]:

定理1: 若, 存在, 对于每个序列, 上存在次数至多为的唯一多项式, 使得对所有, 都有.

定理2: 令是上次数为的多项式, 则对于均匀随机的, 的概率以为上界.

有了以上两个定理, 可将检验乘法三元组正确性的协议从扩展到.

令是次数的Galois扩环. 首先, 可以将上的秘密共享方案扩展到上, 即秘密共享上给定多项式的每个系数. 可以通过使用上的底层乘法来计算上满足security up to additive attacks的秘密共享元素的乘法. 若各参与方将秘密共享形式的三元组看成是上的常数多项式的秘密共享, 则在上的协议也适用于: 存在插值所需的必要序列, 满足定理1和, 且根据定理2, 最终检验是可靠的. 取足够大的, 使得恶意敌手通过验证的概率可以忽略不计.

6.2 Random Linear Combinations over

设秘密共享值的集合打开后的结果为, 参与方需要验证对于所有, 都有. 为了在上做到这一点, 使用次数为的Galois扩环. 简单起见, 若整除, 则. 直观地说, 将的元素"packing"到的元素中, 然后在上执行与上相同的检查. 具体过程如下:

设, 是敌手引入的误差. 这在上可以写成, , 其中是敌手已知的信息. 验证通过, 当且仅当. 假设存在, 则存在. 对, 固定和, 上述等式可以看成是对上的次数为1的多项式求值,  根据定理2, 在随机点求值得到0的概率至多为, 因此敌手作恶但能通过检验的概率可忽略不计.

References

[1] I. Damgård and J. B. Nielsen. Scalable and unconditionally secure multiparty computation. CRYPTO'07.

[2] I. Damgård, M. Keller, E. Larraia, V. Pastro, P. Scholl, and N. P. Smart. Practical covertly secure MPC for dishonest majority - or: Breaking the SPDZ limits. ESORICS'13.

[3] V. Goyal and Y. Song. Malicious security comes free in honest-majority mpc. Cryptology ePrint Archive, Report 2020/134, 2020.

[4] A. Ben-Efraim, M. Nielsen, and E. Omri. Turbospeedz: Double your online SPDZ! Improving SPDZ using function dependent preprocessing. ACNS'19.

[5] E. Ben-Sasson, S. Fehr, and R. Ostrovsky. Near-linear unconditionally-secure multiparty computation with a dishonest minority. CRYPTO'12.

[6] M. Abspoel, R. Cramer, I. Damgård, D. Escudero, and C. Yuan. Efficient information-theoretic secure multiparty computation over  via galois rings. TCC'19.

往期推荐