1、多方安全计算背景
多方安全计算的研究主要是针对无可信第三方的情况下,如何安全地计算一个约定函数的问题。多方安全计算是电子选举、门限签名以及电子拍卖等诸多应用得以实施的密码学基础。
一个多方安全计算协议,如果对于拥有无限计算能力攻击者而言是安全的,则称作是信息论安全的或无条件安全的;如果对于拥有多项式计算能力的攻击者是安全的,则称为是密码学安全的或条件安全的。
已有的结果证明了在无条件安全模型下,当且仅当恶意参与者的人数少于总人数的1/3时,安全的方案才存在。而在条件安全模型下,当且仅当恶意参与者的人数少于总人数的一半时,安全的方案才存在。
安全多方计算起源于1982年姚期智的百万富翁问题,问题就是2个富豪要比对资产,但是又不希望将自己资产暴露出来。
对于多方安全计算的分类主要分为如下几类:
- 不经意传输和混淆电路
- 不经意传输:发送者具有多个秘密数据,将其中一个秘密数据发送给接受者,接受者除了知道已接收的秘密数据而不知道发送者的其他秘密数据,发送者也无法知道发给接收者的秘密数据
- 混淆电路:电路实现主要由与或非门模拟任意计算函数,通过对电路的加密来隐藏实际输入,实现对各个参与者的数据保密,以电路计算实现多方安全计算
- 半诚实模型和恶意模型
- 半诚实参与者:参与者遵守计算协议进行计算过程,但有可能将自己的计算结果透露给攻击者
- 恶意参与者:参与者完全按照攻击者的要求执行计算任务,不但将输入数据和计算结果泄露给攻击者,而且根据攻击者的意图篡改数据,甚至终止协议。
- 安全两方计算和多方安全计算
- 安全两方计算:是多方安全计算的特殊形式,仅仅只有两位计算参与者,两方计算概念定义方式有两种,第一种是功能函数的输出分布计算不可区分性,也称为两方保密计算;第二种是采用实际需求分析和理想函数框架定义。
- 多方安全计算:计算参与者数量较多,并且协议的设计是为了抵抗任意敌手的攻击,其中有参与者之间相互串通修改计算结果或不合法的输入导致计算协议终止,与安全两法计算协议不同,无论敌手情况还是编译器构造都是比较复杂的。
- 通用协议和具体问题协议
- 通用协议:Yao将多方安全计算的功能函数抽象为混淆门的电路,实现对任意函数的计算,经过不断的优化提高了计算效率,但此方案只适用于半诚实模型,在恶意模型下,利用通用编译器的方法,借助比特承诺与零知识证明等工具编译协议,但执行效率较低
多方安全计算的两大类设计方法:
- 混淆电路方法
- 秘密分享方法
2、混淆电路
混淆电路:混淆电路是一种密码学协议,完成参与方能在互相不知晓对方数据的情况下计算某一能 被逻辑电路表示的函数。通过对电路进行加密来掩盖电路的输入和电路的结构,以此来实现对各个参与者的隐私信息的保密,再通过电路计算来实现安全多方计算的目标函数的计算。
3、秘密分享方法
秘密分享:它是指将一个秘密分发给一组参与方,每个参与方只获得这个秘密的一部分,这样一个或少数几个参与方无法还原出原始数据(秘密),只有满足一定数量的参与方把各自的数据凑在一起,才能还原真实数据。