秘密比较PPT课件.ppt

安全多方计算 秘密比较 报告人 唐璇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 除此以外 不知道其他的输入 输出信息 如果存在一个可信的第三方 那么可信第三方通过收集各个秘密输入来计算函数f 然后将输出yi秘密的传给各个参与方 很容易的解决这个安全多方计算问题 但是在现实中非常不容易找到满足条件的第三方 安全多方计算的研究主要是针对在无可信第三方的情况下设计一个安全的多方计算协议 让各个参与者进行安全的合作计算 3 安全多方计算模型 参与方 诚实参与方 半诚实参与方 恶意参与方攻击者 被动攻击者 主动攻击者计算模型半诚实模型 TheSemi honestModel 恶意模型 TheMaliciousModel 此模型下SMC研究是难点通信信道模型 同步模型 异步模型 安全信道 点对点安全信道 带广播的安全信道 目前主要 安全性定义保密性 正确性 独立输入性 保密输出 公平性 恶意行为 开始时拒绝参与协议 更换自己的输入 在协议进行中终止协议 4 安全多方计算基本密码学工具同态加密 哈希函数 秘密共享 零知识证明 茫然传输目前主要研究的安全多方计算问题有 安全数据比较问题 安全多方计算几何问题 保护私有信息的查询问题 安全多方集合计算问题 安全电子拍卖问题 保护私有信息的数据挖掘问题 线性系统背景下安全多方计算问题等等 著名密码学家Goldwasser曾经说过 安全多方计算今天所处的地位正是公开密钥密码10多年前所处的地位 它是密码学研究中一个非常重要的工具 它在计算科学中的应用才刚刚开始 丰富的理论将使它成为计算科学中一个必不可少的组成部分 安全多方计算协议的一个基础问题 基础协议模块 5 茫然传输协议 6 2秘密比较 问题的提出姚氏百万富翁问题的提出打开了数据比较问题的大门 后续又出现了社会主义的百万富翁问题以及一些扩展问题 对保护私有信息的数据比较问题也不仅仅局限于数据大小的比较 还扩展到单个数据甚至向量的相等性比较和排序问题的研究等等 现在 保护私有数据的比较问题已经作为安全多方计算解决方案的基本模块 引起人们对其广泛地关注与研究 保护私有信息的数据比较问题 7 姚氏百万富翁问题研究现状1982年 姚氏百万富翁协议 O 2n 2003年 Ioannidis等人 基于协议 O d2 2004年 Blake等人使用Paillier加同态密码体制设计了一个秘密比较协议 其时间复杂度和计算复杂度都为O nlogN 2004年 Schoenmakers等人利用同态门限ElGamal方案的安全乘法协议提出了一个解决加密的输入输出的整数的安全比较的方案 他们的方案要求线性轮O m 和安全乘法门 2005年 李顺东等人构造特殊函数 利用不经意传输协议 电子学报 2005年 Lin等人 对保密输入进行特殊0 1编码 并且基于ElGamal乘法同态加密算法 比较问题 判断两个集合是否相交问题 从而设计了一个百万富翁协议 数据比较问题 区间之间比较 不可信第三方协议缺点 必须在双方数据不相等的前提下 同态加密体制茫然传输协议不可信第三方 8 2006年 Damgard等人在无条件安全环境下 利用线性秘密分享方案设计一个保护私有信息的数据比较协议 2008年 Jin等人提出了一个百万富翁问题的扩展问题 即向量优势问题 这个问题可以描述为两个参与方 各自拥有向量A a1 a2 an B b1 b2 bn 问题的输出就是想知道是否对于所有的i 都有ai bi 并且都不向对方泄露自己的输入 作者在半诚实模型和恶意模型下都研究了向量优势问题 并且给出了不同轮数的协议 9 2011 ACM 安全两方计算公平性 被引68次 2011 安全多方计算 从百万富翁问题到匿名者 被引3次 2011 安全多方计算排序问题 被引4次 ScienceChinaInformationSciences2013 Yao smillionaires problemanddecoy basedpublickeyencryptionbyclassicalphysics通过经典物理学的姚氏百万富翁问题和诱捕式公钥加密2013 FairTwo PartyComputationsviatheBitCoinDeposits 被引2次 10 姚氏百万富翁问题 协议一 姚氏百万富翁协议 O 2n 11 协议二 基于协议的保护私有信息的数据比较协议假设Alice和Bob的数据都小于2d 步骤1 Alice随机生成一个数据全为k比特的d 2阶矩阵A 其中k为协议的密钥长度 然后随机选择r和足够大的S 满足0 r 2k s k 步骤2 令Aijl表示元素Aij的第l比特值 Aij0表示最不重要的比特 对于每个i 1 i d Alice进行以下操作 对每个j s 令Ai1j和Ai2j为随机比特 如果ai 1 则l 1 否则l 2 对每个 0 j 2i 1 令Ailj为随机比特位 12 设m 2i 令 1 ai 对于每个i 1 i d 构造一个随机k比特数Si 构造一个除了最高两位以外其余各位都是随机的数Sd 令对于对l 1 2 令 leftrot AilSi r 其中lefttrot x y 表示用y比特对左边的数x进行旋转操作 步骤3 对于每个i 1 i d Bob通过不经意传输 其中l bi 1 步骤4 Alice发送S lefttrot Sj r 给Bob 步骤5 Bob用获得的数据和S进行异或运算 从左向右扫描知道到达连续0的个数最大的数目 O d2 13 协议三 保护私有信息的较小数的比较协议协议四 保护私有信息的任意两数的比较协议 长度函数茫然传输 14 协议五 基于同态加密的百万富翁问题高效解决方案协议思想 对保密输入进行0编码和1编码 将自然数编码成一个集合从而把数据比较问题转化为集合的相交问题 并利用ElGamal同态加密算法解决了这个问题 这是一个很有创意的协议 0 编码和1 编码GTProtocol C类会议 ACNS 被引64次 15 引用协议五的文献 2010 计算机工程 通过采用0编码与1编码 将百万富翁问题转换为集合交集问题 提出一种基于可交换加密函数的百万富翁问题高效解决方案 加解密O n 通信轮数为42011年 黄山学院 该协议在比较出 的关系上增加了比较 的关系同时还给出协议的正确性安全性和效率的分析2013年 电子学报 李顺东等人 基于同态加密的高效多方保密计算 将保密的数据编码成一个向量 在加法同态加密算法基础上设计一个简洁 高效而且通用的解决方案 将两个数的保密比较问题归约到向量的部分标量积 scalarproduct 的保密计算问题 16 社会主义百万富翁问题 在姚氏百万富翁问题的研究屮 只是知道了两个数a和b的大小关系 a b或a b 而社会主义百万富翁问题主要解决a与b是否相等 协议一 基于DL DH DDH假设的社会主义百万富翁协议 2001年 协议二 基于 隐藏假设的社会主义百万富翁协议 2004年 协议三 基于滑动窗口和交换加密函数的社会主义百万富翁协议 半诚实模型下 2007年 总结 同时 目前现有数据比较协议中也大多是要么只解决百万富翁问题 要么只解决社会主义百万富翁问题 并且 目前存在的同时解决两个问题的方案也是局限于整数范围内 17 排序问题 保护私有信息的排序问题 百万富翁的扩展问题 保护私有信息的两方整数排序协议 2008 保护私有信息的多方排序协议 2008 基于ElGamal的保护私有信息的数据排序协议 2007 基于秘密共享的保护私有信息的排序协议 2011 18 协议一 AFairandEfficientSolutionto