安全多方计算(也称为安全计算,多方计算/ MPC或隐私保护计算)是密码学的一个领域。
MPC处理的问题是在一组可能相互不信任的各方之间共同计算一个函数,同时阻止任何参与者了解有关其他方提供的输入的任何信息;同时(在可能的范围内)确保获得正确的输出。
MPC计算基于计算输入(和中间结果)的秘密共享。
秘密共享最初由Adi Shamir提出,将数据分为几部分,它们本身是一些随机数,但是当组合在一起时(例如,通过加法)恢复原始数据。
MPC依赖于将每个数据输入项划分为两个或更多份额,并将其分配给计算方。加法和乘法的同态特性使那些当事方可以计算份额以达到共享结果,这些结果相结合可得出计算函数的正确输出。
为了执行MPC所需的共享计算,所有参与计算的方都遵循一个“协议”:一组指令和相互通信,当这些方遵循时,它们将实现分布式计算机程序
能够抵抗隐蔽或恶意对手的现代MPC协议还依赖于诚实参与者可使用的零知识证明来检测不良行为(并通常消除不诚实的一方)。
应用实例
MPC已有许多用例。
端到端的加密关系数据库原型,使用MPC来对仅以加密形式保存在数据库中的数据计算SQL查询的答案。
统计分析语言(例如R)已经增强了MPC功能,可以在统计和其他计算过程中保护数据。
MPC还可用于保护密钥,同时将这些密钥用于加密,解密和签名。
MPC还用于流数据环境中,例如处理VoIP数据以进行电话会议,而无需VoIP系统中的任何受信服务器。
最近的一篇论文更详细地描述了一些主要的用例。MPC的一项有趣的潜在应用是长期共享数据治理。
由于MPC依赖于秘密共享,并具有对所有相关方共同控制的那些共享的访问控制的权限。因此数据可以以机密共享形式无限期地存储,并且只有在适当比例的各方同意的情况下,才可以恢复数据。此功能与静止数据秘密共享的概念有关,而与阈值加密的概念关系更远。
敌手模型和安全性争论
因为MPC假定了互不信任的各方的可能性,所以它也假定了新的一类对手:控制计算中的一个或多个参与者的对手。
这样的对手可能是内部威胁,也可能是组织外部的特洛伊木马或其他渗透性很长的攻击。
这类新型的攻击者通常用几个特征来描述:诚实度,移动度和受害计算方的比例是文献中描述的典型特征。
在半诚实的对手模型中,这种控制仅限于检查损坏的参与者看到的所有数据以及对他们联合运行的计算程序的无限了解。
在“隐蔽”模型中,对手通常会将控制权扩展到修改或破坏商定的协议,其目的通常是要学习更多的知识,而不仅仅是从观察中学习到的知识。
但是,在这种模型中,攻击者被激励保持其存在不被察觉,从而限制了其可能采取的行动。在恶意模型中,攻击者还可能修改或破坏商定的协议,但无意将其存在隐藏起来。结果,恶意对手可能会采取比秘密对手更大范围的行动。
固定对手模型假设对手选择了参与者会影响的先验条件。例如,这种模型可能表示一个计算参与者受到了损害,而其他人则没有受到损害。此对手移动性特征的增强版本允许对手在计算期间在参与者之间移动。目前,很难想象这样一个对手的真实世界。
MPC对手的假设属于两类之一:诚实多数和不诚实多数
就像有各种各样的MPC参与者对手模型一样,也有各种各样的MPC协议提供安全性参数来防御那些对手。
安全性通常是通过显示MPC协议的实际执行与理想化的仿真器相区分的,在理想化的仿真器中,所有计算方将其私人输入发送给可信任的经纪人,该经纪人计算商定的功能并返回输出。各种MPC协议具有增强安全性的不同属性。通常描述的那些属性是:
●输入隐私权,如上文所述
●输出正确性–接收输出的各方都会收到正确的输出
●公平性–打算接收输出的所有各方都这样做,或者没有接收到
●保证输出–所有诚实的方都得到保证能够正确完成计算,而不受不诚实方的攻击行动。
虽然当大多数计算方不遵循协议时可以保证输入隐私和输出正确性,但是只有当大多数计算方遵循协议时,才能保证所有四个所需属性(输入隐私,输出正确性,公平性和有保证的输出交付)的组合。
历史
MPC最初于1982年作为安全的两方计算(2PC)正式推出(针对所谓的百万富翁问题),1986年由Andrew Yao正式引入。该领域也称为安全函数计算(SFE)。两方计算随后被Goldreich,Micali和Widgerson推广到多方。
应当指出,MPC经常需要计算方之间交互。实际上,使用通信成本作为唯一估计因子(即完全忽略计算方的计算延迟估计),对MPC协议的运行时间的估计可能非常准确。
双方之间对可用网络带宽和网络延迟的高度依赖一直使MPC处于理论上的应用。直到2000年代中期,对协议的改进导致人们认识到MPC不仅可能,而且可以在互联网上进行有用的计算。
在一些特定的应用场景下,MPC可以成为有效的解决方案(尤其是那些需要在股票上进行本地操作且各方之间没有太多交互的场景)。
分布式投票,保护隐私的竞价和拍卖,共享签名或解密功能以及密文检索都是具有这些特性的应用场景。
多方计算的第一个大规模实际应用(在一个实际的拍卖问题上展示)于2008年1月在丹麦进行。
使用技术成本
MPC技术的性能在很大程度上取决于安全计算的功能。MPC性能的典型指标是计算速度,MPC中计算延迟与没有MPC安全性时完成相同计算的延迟之比。
对于一般计算,例如处理典型的关系数据库查询运算符所需的计算,最新结果显示速度降低了10000倍。
在MPC中,如果计算依赖于加法(例如求和),其通常比常规计算快,而依赖除法或其他更复杂函数的计算通常要慢很多。与依赖浮点计算的计算相比,对整数或定点数据的计算相对较快。对于依赖于生成功能(例如随机数生成)的计算通常也很慢。
下表总结了实际的示例应用程序以及这些计算得出的典型速度下降。
可用性
在大多数情况下,MPC仍然是一个学术研究主题。少数公司使用专门的MPC协议来实现特定功能,而少数公司专门从事此技术的标准或定制产品开发或解决方案咨询。
尽管MPC的操作理论处于相对较高的技术准备状态,但最终用户对计算产品的大多数期望仍处于早期开发阶段。
同样,MPC目前很难正确配置,并且当前需要高度定制的客户端软件以及用于部署的服务器软件。虽然概念验证的演示者已经表明可以开发这些重要功能,但从产品意义上来说开发尚处于非常早期的阶段。
MPC可以在关系数据库上执行查询,但只能对关系查询和数据类型的有限子集执行,而MPC无法容纳重要的相关操作,例如数据清理。
MPC系统的性能仍然是一个挑战,与“明文”计算相比,减速系数要达到100倍,最高可达100000倍或更高。