1、 SMC安全多方计算安全多方计算 秘密比较秘密比较报告人：唐璇报告人：唐璇 2014.03 2014.031目录1 安全多方计算（SMC） 基本知识 基本密码学工具目前SMC研究问题2 秘密比较问题研究进展 姚氏百万富翁协议 社会主义百万富翁协议 排序问题21 安全多方计算n 安全多方计算 安全多方计算的数学化定义如下： 假设有n个参与方P1，.，Pn，每一个参与方都有一个秘密输入mi (i = 1,2, ,n)。这n个参与者共同执行一个协议 来计算函数f(m1,.,mn) = (y1,.,yn)。计算结束后,每个参与者Pi仅能得到自己的输出yi，除此以外，不知道其他的输入、输出信息。 如果存
2、在一个可信的第三方，那么可信第三方通过收集各个秘密输入来计算函数f，然后将输出yi秘密的传给各个参与方,很容易的解决这个安全多方计算问题。但是在现实中非常不容易找到满足条件的第三方。 安全多方计算的研究主要是针对在无可信第三方的情况下设计一个安全的多方计算协议，让各个参与者进行安全的合作计算。3安全多方计算模型n 参与方参与方：诚实参与方、半诚实参与方、恶意参与方n 攻击者攻击者：被动攻击者、主动攻击者n 计算模型计算模型 半诚实模型（The Semi-honest Model） 恶意模型(The Malicious Model)：此模型下SMC研究是难点难点n 通信信道模型通信信道模型：同步
3、模型、异步模型安全信道：点对点安全信道、带广播的安全信道(目前主要)n 安全性定义安全性定义 保密性、正确性、独立输入性、保密输出、公平性恶意行为：开始时拒绝参与协议、更换自己的输入、在协议进行中终止协议。4n 安全多方计算基本密码学工具 同态加密、哈希函数、秘密共享、零知识证明、茫然传输n 目前主要研究的安全多方计算问题有 安全数据比较问题安全数据比较问题、安全多方计算几何问题、保护私保护私有信息的查询问题有信息的查询问题、安全多方集合计算问题 安全电子拍卖问题、保护私有信息的数据挖掘问题、线性系统背景下安全多方计算问题等等。n 著名密码学家Goldwasser曾经说过：安全多方计算今天所处
4、的地位正是公开密钥密码10多年前所处的地位。它是密码学研究中一个非常重要的工具，它在计算科学中的应用才刚刚开始，丰富的理论将使它成为计算科学中一个必不可少的组成部分。” 安全多方计算协议的一个基础问题，基础协议模块5 SMC茫然传输协议62 秘密比较n 问题的提出 姚氏百万富翁问题的提出打开了数据比较问题的大门，后续又出现了社会主义的百万富翁问题以及一些扩展问题。 对保护私有信息的数据比较问题也不仅仅局限于数据大小的比较，还扩展到单个数据甚至向量的相等性比较和排序问题的研究等等。 现在，保护私有数据的比较问题已经作为安全多方计算解决方案的基本模块，引起人们对其广泛地关注与研究。保护私有信息的数
5、据比较问题7 n 姚氏百万富翁问题研究现状1982年，姚氏百万富翁协议，O(2n)2003年，Ioannidis等人，基于 协议；O(d2)；2004年，Blake等人使用Paillier加同态密码体制设计了一个秘密比较协议,其时间复杂度和计算复杂度都为O(nlogN)。2004年，Schoenmakers等人利用同态门限ElGamal方案的安全乘法协议提出了一个解决加密的输入输出的整数的安全比较的方案。他们的方案要求线性轮O(m)和安全乘法门。2005年，李顺东等人构造特殊函数，利用不经意传输协议；（电子学报） 2005年，Lin等人，对保密输入进行特殊0/1编码，并且基于ElGamal乘法
6、同态加密算法，比较问题判断两个集合是否相交问题，从而设计了一个百万富翁协议。（数据比较问题区间之间比较）只适用于比较两个较小的数，针对较大秘密数据的比较问题：1996年，Jakobsson,多轮迭代多轮迭代；该协议的复杂性是多项式级的，其幂次为O(k)；1999年，Cachin引入一个不可信第三方，提出了一个高效的秘密比较方案并用于拍卖中；该方案基于?-隐藏假设以及同态加密的语义安全性；对位长为l的数据进行比较，通信复杂度为O(l)；2004年，秦静等人的改进，提出了两个高效的协议来完成秘密比较；OT21不可信第三方协议缺点：必须在双方数据不相等的前提下同态加密体制茫然传输协议不可信第三方82
7、006年，Damgard等人在无条件安全环境下,利用线性秘线性秘密分享密分享方案设计一个保护私有信息的数据比较协议。2008年，Jin等人提出了一个百万富翁问题的扩展问题,即向量优势向量优势问题。这个问题可以描述为两个参与方,各自拥有向量A=(a1,a2, an),B = (b1,b2, ,bn),问题的输出就是想知道是否对于所有的i,都有ai bi,并且都不向对方泄露自己的输入。作者在半诚实模型和恶意模型下都研究了向量优势问题,并且给出了不同轮数的协议。9n 2011，ACM，安全两方计算公平性(被引68次)；n 2011，安全多方计算：从百万富翁问题到匿名者(被引3次)n 2011，安全多
8、方计算排序问题(被引4次)，Science China Information Sciencesn 2013，Yaos millionaires problem and decoy-based public key encryption by classical physics 通过经典物理学的姚氏百万富翁问题和诱捕式公钥加密n 2013,Fair Two-Party Computations via the BitCoin Deposits(被引2次)10姚氏百万富翁问题n 协议一：姚氏百万富翁协议O(2n)11n 协议二：基于 协议的保护私有信息的数据比较协议 假设Alice和Bob的数据
9、都小于2d。 步骤1:Alice随机生成一个数据全为k比特的d2阶矩阵A,其中k为 协议的密钥长度,然后随机选择r和足够大的S,满足0r 2k，sk。 步骤2:令Aijl表示元素Aij的第l比特值，Aij0表示最不重要的比特。对于每个i (1id)，Alice进行以下操作: 对每个js,令Ai1j和Ai2j为随机比特； 如果ai=1,则l=1,否则l=2；对每个(0j2i-1),令Ailj 为随机比特位;OT21OT2112 设m=2i，令 = 1, = ai; 对于每个i(1id),构造一个随机k比特数Si,构造一个除了最高两位以外其余各位都是随机的数Sd,令 对于对l=1,2,令 =lef
10、trot(Ail Si, r),其中lefttrot(x,y)表示用y比特对左边的数x进行旋转操作。步骤3:对于每个i (1id), Bob通过不经意传输 ,其中l=bi+1。步骤4: Alice发送S=lefttrot( Sj,r)给Bob。步骤5: Bob用获得的数据和S进行异或运算,从左向右扫描知道到达连续0的个数最大的数目。A1milAmilA1ilA1ild1jO(d2)13n 协议三：保护私有信息的较小数的比较协议n 协议四：保护私有信息的任意两数的比较协议长度函数茫然传输14 n 协议五：基于同态加密的百万富翁问题高效解决方案协议思想：对保密输入进行0编码和1编码，将自然数编码成
11、一个集合从而把数据比较问题转化为集合的相交问题，并利用ElGamal同态加密算法解决了这个问题，这是一个很有创意的协议。0-编码和1-编码GT Protocol:C类会议，ACNS，被引64次15n (引用协议五的文献) 2010，计算机工程，通过采用0编码与1编码，将百万富翁问题转换为集合交集问题，提出一种基于可交换加密函数的百万富翁问题高效解决方案，加解密O(n),通信轮数为4 2011年，黄山学院，该协议在比较出“”的关系上增加了比较“= =”的关系同时还给出协议的正确性安全性和效率的分析 2013年，电子学报，李顺东等人，基于同态加密的高效多方保密计算 将保密的数据编码成一个向量，在加
12、法同态加密算法基础上设计一个简洁、高效而且通用的解决方案，将两个数的保密比较问题归约到向量的部分标量积(scalarproduct)的保密计算问题；16社会主义百万富翁问题v 在姚氏百万富翁问题的研究屮，只是知道了两个数a和b的大小关系：ab或a b。而社会主义百万富翁问题主要解决a与b是否相等。协议一：基于DL-DH-DDH假设的社会主义百万富翁协议(2001年)协议二：基于?-隐藏假设的社会主义百万富翁协议(2004年)协议三：基于滑动窗口和交换加密函数的社会主义百万富翁协议(半诚实模型下)(2007年)v 总结：同时，目前现有数据比较协议中也大多是要么只解决百万富翁问题，要么只解决社会主
13、义百万富翁问题。并且，目前存在的同时解决两个问题的方案也是局限于整数整数范围内。17排序问题n 保护私有信息的排序问题（百万富翁的扩展问题） 保护私有信息的两方整数排序协议（2008） 保护私有信息的多方排序协议（2008） 基于ElGamal的保护私有信息的数据排序协议（2007） 基于秘密共享的保护私有信息的排序协议（2011）18n 协议一：A Fair and Efficient Solution to the Socialist Millionaires Problem, Discrete Applied Mathematics(2001被引95次) 公平高效的社会主义百万富翁问题解决方案，O(k)n 协议二：无信息泄露的比较协议(软件学报，2004)n 协议三：刘文等人，基于滑动窗口和交换加密函数解决SMP的新方案(计算机工程，2007)19 SMC20
