秘密比较课件.ppt
《秘密比较课件.ppt》由会员分享,可在线阅读,更多相关《秘密比较课件.ppt(20页珍藏版)》请在三一办公上搜索。
1、安全多方计算 秘密比较,报告人:唐璇 2014.03,1,目录,1 安全多方计算(SMC) 基本知识 基本密码学工具目前SMC研究问题2 秘密比较问题研究进展 姚氏百万富翁协议 社会主义百万富翁协议 排序问题,2,1 安全多方计算,安全多方计算安全多方计算的数学化定义如下: 假设有n个参与方P1,.,Pn,每一个参与方都有一个秘密输入mi (i = 1,2, ,n)。这n个参与者共同执行一个协议 来计算函数f(m1,.,mn) = (y1,.,yn)。计算结束后,每个参与者Pi仅能得到自己的输出yi,除此以外,不知道其他的输入、输出信息。如果存在一个可信的第三方,那么可信第三方通过收集各个秘密
2、输入来计算函数f,然后将输出yi秘密的传给各个参与方,很容易的解决这个安全多方计算问题。但是在现实中非常不容易找到满足条件的第三方。安全多方计算的研究主要是针对在无可信第三方的情况下设计一个安全的多方计算协议,让各个参与者进行安全的合作计算。,3,安全多方计算模型,参与方:诚实参与方、半诚实参与方、恶意参与方攻击者:被动攻击者、主动攻击者计算模型半诚实模型(The Semi-honest Model)恶意模型(The Malicious Model):此模型下SMC研究是难点通信信道模型:同步模型、异步模型安全信道:点对点安全信道、带广播的安全信道(目前主要)安全性定义 保密性、正确性、独立输
3、入性、保密输出、公平性,恶意行为:开始时拒绝参与协议、更换自己的输入、在协议进行中终止协议。,4,安全多方计算基本密码学工具 同态加密、哈希函数、秘密共享、零知识证明、茫然传输目前主要研究的安全多方计算问题有 安全数据比较问题、安全多方计算几何问题、保护私有信息的查询问题、安全多方集合计算问题 安全电子拍卖问题、保护私有信息的数据挖掘问题、线性系统背景下安全多方计算问题等等。著名密码学家Goldwasser曾经说过:安全多方计算今天所处的地位正是公开密钥密码10多年前所处的地位。它是密码学研究中一个非常重要的工具,它在计算科学中的应用才刚刚开始,丰富的理论将使它成为计算科学中一个必不可少的组成
4、部分。”,安全多方计算协议的一个基础问题,基础协议模块,5,茫然传输协议,6,2 秘密比较,问题的提出 姚氏百万富翁问题的提出打开了数据比较问题的大门,后续又出现了社会主义的百万富翁问题以及一些扩展问题。 对保护私有信息的数据比较问题也不仅仅局限于数据大小的比较,还扩展到单个数据甚至向量的相等性比较和排序问题的研究等等。 现在,保护私有数据的比较问题已经作为安全多方计算解决方案的基本模块,引起人们对其广泛地关注与研究。,保护私有信息的数据比较问题,7,姚氏百万富翁问题研究现状1982年,姚氏百万富翁协议,O(2n)2003年,Ioannidis等人,基于 协议;O(d2);2004年,Blak
5、e等人使用Paillier加同态密码体制设计了一个秘密比较协议,其时间复杂度和计算复杂度都为O(nlogN)。2004年,Schoenmakers等人利用同态门限ElGamal方案的安全乘法协议提出了一个解决加密的输入输出的整数的安全比较的方案。他们的方案要求线性轮O(m)和安全乘法门。2005年,李顺东等人构造特殊函数,利用不经意传输协议;(电子学报) 2005年,Lin等人,对保密输入进行特殊0/1编码,并且基于ElGamal乘法同态加密算法,比较问题判断两个集合是否相交问题,从而设计了一个百万富翁协议。(数据比较问题区间之间比较),不可信第三方协议缺点:必须在双方数据不相等的前提下,同态
6、加密体制茫然传输协议不可信第三方,8,2006年,Damgard等人在无条件安全环境下,利用线性秘密分享方案设计一个保护私有信息的数据比较协议。2008年,Jin等人提出了一个百万富翁问题的扩展问题,即向量优势问题。这个问题可以描述为两个参与方,各自拥有向量A=(a1,a2, an),B = (b1,b2, ,bn),问题的输出就是想知道是否对于所有的i,都有ai bi,并且都不向对方泄露自己的输入。作者在半诚实模型和恶意模型下都研究了向量优势问题,并且给出了不同轮数的协议。,9,2011,ACM,安全两方计算公平性(被引68次);2011,安全多方计算:从百万富翁问题到匿名者(被引3次)20
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 秘密 比较 课件
链接地址:https://www.31ppt.com/p-1454445.html