- 1、下载文档前请自行甄别文档内容的完整性,平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益,请联系客服反馈,我们会尽快为您处理(人工客服工作时间:9:00-18:30)。
3
安全多方计算模型
参与方:诚实参与方、半诚实参与方、恶意参与方
攻击者:被动攻击者、主动攻击者
计算模型
恶意行为:
• 半诚实模型(The Semi-honest Mode开更l)始换时自拒己绝的参输与入协、议、
• 恶意模型(The Malicious Model):此模在型协议下进S行M中C终研止协议。
SMC
安全多方计算
——秘密比较
报告人:唐璇 2014.03
1
目录
1 安全多方计算(SMC) ① 基本知识 ② 基本密码学工具 ③目前SMC研究问题 2 秘密比较问题研究进展 ① 姚氏百万富翁协议 ② 社会主义百万富翁协议 ③ 排序问题
2
1 安全多方计算
安全多方计算 • 安全多方计算的数学化定义如下:
public key encryption by classical physics 通过经典物理学的姚氏百万富翁问题和诱捕式公钥加密 2013,Fair Two-Party Computations via the BitCoin Deposits(被引2次)
10
姚氏百万富翁问题
协议一:姚氏百万富翁协议
O(2n)
11
协议二:基于OT12 协议的保护私有信息的数据比较协议 假设Alice和Bob的数据都小于2d。 步骤1:Alice随机生成一个数据全为k比特的d×2阶矩阵 A,其中k为OT12 协议的密钥长度,然后随机选择r和足够大 的S,满足0≤r<2k,s<k。 步骤2:令Aijl表示元素Aij的第l比特值,Aij0表示最不重要 的比特。对于每个i (1≤i≤d),Alice进行以下操作:
假设有n个参与方P1,...,Pn,每一个参与方都 有一个秘密输入mi (i = 1,2,…… ,n)。这n个参与者共同 执行一个协议 来计算函数f(m1,...,mn) = (y1,...,yn)。 计算结束后,每个参与者Pi仅能得到自己的输出yi,除此 以外,不知道其他的输入、输出信息。 • 如果存在一个可信的第三方,那么可信第三方通过收 集各个秘密输入来计算函数f,然后将输出yi秘密的传 给各个参与方,很容易的解决这个安全多方计算问题。 但是在现实中非常不容易找到满足条件的第三方。 • 安全多方计算的研究主要是针对在无可信第三方的情 况下设计一个安全的多方计算协议,让各个参与者进 行安全的合作计算。
8
2006年,Damgard等人在无条件安全环境下,利用线性秘 密分享方案设计一个保护私有信息的数据比较协议。
2008年,Jin等人提出了一个百万富翁问题的扩展问题,即 向量优势问题。这个问题可以描述为两个参与方,各自拥 有向量A=(a1,a2,……, an),B = (b1,b2,…… ,bn),问题的输 出就是想知道是否对于所有的i,都有ai > bi,并且都不向 对方泄露自己的输入。作者在半诚实模型和恶意模型下 都研究了向量优势问题,并且给出了不同轮数的协议。
2003年,Ioannidis等人,基O于T12 协议;O(d2);
①同态加密体制
220000时44年年间,,复BS杂clah度koe和e等n计m人算a使k复e用r杂sP等度ai人l都lie利为r加用O同同(n态l态o密g门N码限)。体El制Ga设m计al了方一案个的②③秘安茫不密全然可比乘传信较法输第协协协三议议议方,提其
9
2011,ACM,安全两方计算公平性(被引68次); 2011,安全多方计算:从百万富翁问题到匿名者(被引3
次) 2011,安全多方计算排序问题(被引4次),Science China
Information Sciences 2013,Yao's millionaires' problem and decoy-based
姚氏百万富翁问题的提出打开了数据比较问题的 大门,后续又出现了社会主义的百万富翁问题以及一 些扩展问题。
对保护私有信息的数据比较问题也不仅仅局限于 数据大小的比较,还扩展到单个数据甚至向量的相保护私有数据的比较问题已经作为安全多 方计算解决方案的基本模块,引起人们对其广泛地关 注与研究。
究是难点
通信信道模型:同步模型、异步模型
—安全信道:点对点安全信道、带广播的安全信道(目前 主要)
安全性定义
保密性、正确性、独立输入性、保密输出、公平性
4
安全多方计算基本密码学工具 安全多方同计算态协加议密的一、个哈希函数、秘密共享、零知识证明、茫然 基础问传题输,基础协议模块
目前主要研究的安全多方计算问题有 — 安全数据比较问题、安全多方计算几何问题、保护 私有信息的查询问题、安全多方集合计算问题 — 安全电子拍卖问题、保护私有信息的数据挖掘问题 、线性系统背景下安全多方计算问题等等。
7
姚氏百万富翁问题研究现状
①不可信第三方
1982年,姚氏百万富翁协议,O(2n)
②协议缺点:必须在双方 数据不相等的前提下
只适用于比较两个较小的数,针对较大秘密数据的比较问题:
1996年,Jakobsson,多轮迭代;该协议的复杂性是多项式级的,其幂次为O(k); 1999年,Cachin引入一个不可信第三方,提出了一个高效的秘密比较方案并用于 拍卖中;该方案基于ϕ-隐藏假设以及同态加密的语义安全性;对位长为l的数据进行 比较,通信复杂度为O(l); 2004年,秦静等人的改进,提出了两个高效的协议来完成秘密比较;
出了一个解决加密的输入输出的整数的安全比较的方案。他们的方案要求
线性轮O(m)和安全乘法门。
2005年,李顺东等人构造特殊函数,利用不经意传输协议;(电子学报)
2005年,Lin等人,对保密输入进行特殊0/1编码,并且基于ElGamal乘法同 态加密算法,比较问题→判断两个集合是否相交问题,从而设计了一个百 万富翁协议。(数据比较问题→区间之间比较)
著名密码学家Goldwasser曾经说过:"安全多方计算今 天所处的地位正是公开密钥密码10多年前所处的地位。 它是密码学研究中一个非常重要的工具,它在计算科学 中的应用才刚刚开始,丰富的理论将使它成为计算科学 中一个必不可少的组成部分。”
5
SMC
茫然传输协议
6
2 秘密比较
问题的提出
保护私有信息的数据比较问题