安全排序协议及其应用

安全多方计算（secure multi-party computation,SMC）是国际密码学界近年来的研究热点.排序是一种基本的数据操作,是算法研究中最基础的问题.多方保密排序是百万富翁问题的推广,是一个基本的SMC问题,在科学决策、电子商务推荐、保密招标/拍卖、保密投票以及保密数据挖掘等方面有重要应用.目前已有的安全多方排序解决方案大多只能适用于隐私数据范围已知而且范围较小的情况,如果数据范围未知或者数据范围很大,还未见到有效的解决方案.首先,在数据范围已知情形下,针对同数据并列计位以及增位次计位两种不同排序方式设计保密计算协议,进一步设计基于关键词的增位次计位方式保密排序协议;其次,以这些协议为基础,在数据范围未知的情形下,针对上述两种不同排序方式分别构造有效的保密排序方案.应用该排序协议作为模块,可解决许多以排序为基础的实际应用问题.最后设计了一个安全、高效的保密Vickrey招投标协议,以解决实际保密招标问题.通过灵活运用编码技巧,并基于ElGamal门限密码体制设计协议,这些协议在半诚实模型下是安全、高效的.应用模拟范例严格证明了协议的安全性,并对协议的执行效率进行了实际测试.实验结果表明,该协议是高效的.     

分布式数据集极差与极值和的保密计算

随着信息通信技术的不断突破与发展,信息获取变得非常便利.与此同时,隐私信息也更容易泄露.将智能领域与安全多方计算技术相结合,有望解决隐私保护问题.目前,安全多方计算已经解决了许多不同隐私保护问题,但还有更多的问题等待人们去解决.对于极差、极值和的安全多方计算问题目前研究的结果很少,极差、极值和作为统计学的常用工具在实际中有广泛的应用,研究极差、极值和的保密计算具有重要意义.提出新编码方法,用新编码方法解决了两种不同的安全多方计算问题,一是极差的保密计算问题,二是极值和的保密计算问题.新编码方法结合Lifted ElGamal门限密码系统,设计多方参与、每方拥有一个数据场景下分布式隐私数据集极差的保密计算协议;将新编码方法稍作改动解决相同场景下保密计算极值和的问题.以此为基础,对新编码方法进一步修改,结合Paillier密码系统设计了两方参与、每方拥有多个数据情况下分布式隐私数据集极差、极值和的保密计算协议.用模拟范例方法证明协议在半诚实模型下的安全性.最后,用模拟实验测试协议的复杂性.效率分析和实验结果表明所提协议简单高效,可广泛用于实际应用中,是解决其他很多安全多方计算问题的重要工具...     

向量等分量数的两方保密计算及推广应用

安全多方计算是近年来国际密码学界的研究热点.安全向量计算作为安全多方计算研究的重要内容,也是解决许多实际安全计算问题的基本工具.在科学研究中很多研究对象都可以用向量来刻画,并通过对这些向量进行各种计算从而得到所需结果,这也使安全向量计算在电子商务推荐、保密的分类、保密聚类等研究中得到了广泛应用.本文主要研究向量等分量数计算问题,即保密计算两个向量有多少个对应分量相等,这个问题的研究对于安全多方计算和隐私保护有重要的理论与实际意义.首先设计编码方法对保密向量进行编码,并结合具有加法同态性的Paillier加密方案,针对数据范围有限制和无限制两种不同情形分别设计了高效的保密计算协议,应用模拟范例严格证明了协议的安全性.作为向量等分量数保密计算协议的应用,进一步研究了向量等分量数阈值判定问题和向量优势统计问题的解决方案.并以所设计的协议为基础解决了多个点与区间(或集合)关系判定问题和字符串模式匹配等实际应用问题.复杂性分析和实验测试都表明本文协议是高效和实用的.     

数轴上保密关系测定协议

近些年来,安全多方计算一直是信息安全领域的热点问题之一,已经成为分布式网络用户在协同计算中用于隐私保护的关键技术.信息安全学者已经提出若干安全多方计算问题的解决方案,但更多的安全多方计算问题还有待研究.研究数轴上的保密关系测定问题,着重探讨3个子问题：（1）面向有理数的点（或数）与区间保密关系测定问题;（2）面向有理数的多维点与区间保密关系测定问题;（3）面向有理数的区间与区间保密关系测定问题.数轴上的保密关系测定问题在隐私保护领域有着广泛的应用,可以作为基础模块用于构造其他安全多方计算协议.基于由加密方计算（或选取）加密底数的Paillier变体同态加密方案,设计了3个数轴上的保密关系测定协议：面向有理数的数与区间保密关系测定协议、面向有理数的多维点与区间保密关系测定协议以及面向有理数的区间与区间保密关系测定协议.并在标准模型下,采用模拟范例（ideal/real）分析了3个协议的安全性.这3个协议中的保密比值计算思想直接可以用于解决有理数范围内的百万富翁问题.更广泛地,这3个协议还可以作为基础模块用于解决保密点与圆环区域关系判定问题、点与凸多边型位置关系判定问题、保密近感探测问题等安全多方计算问题.     

云环境下集合隐私计算

多方保密计算是网络空间安全与隐私保护的关键技术,基于同态加密算法的多方保密计算协议是解决云计算安全的一个重要工具.集合隐私计算是多方保密计算的一个基本问题,具有广泛的应用.现有的集合隐私计算方案多是基于两方的情况,基于多方的方案较少,效率较低,且这些方案都不能扩展到云计算平台.本文首先设计了一种新的编码方案,根据新的编码方案和同态加密算法在云计算环境下构造了一个具有普遍适用性且抗合谋的保密计算集合并集问题解决方案.该方案中的同态加密算法既可以是加法同态又可以是乘法同态的加密算法.本文进一步利用哥德尔编码和ElGamal公钥加密算法构造了一种适用于云计算的高效集合并集计算方案.这些方案还可以对多个集合中的所有数据进行保密排序,并证明这些方案在半诚实模型下是安全的.本文中的方案经过简单改造,也可以保密地计算多个集合的交集.     

排序问题的安全多方计算协议

为某些特殊问题构造有效的安全多方计算协议是多方计算研究领域的一个重要分支.文中使用密钥共享方案为排序问题构造了一个有效的安全多方计算协议,该协议在n个参与者中至多只有t个不诚实者,若t≤(n-1)/2,则它在被动攻击下是完全安全的;若t相似文献   

向量等分量数的保密计算及应用

随着信息技术的快速发展,在保护数据隐私的条件下进行多方合作计算变得越来越普及,安全多方计算已经成为解决这类保密计算问题的核心技术.向量的保密计算是安全多方计算的重要研究方向,目前有很多研究成果,包括保密计算向量的点积,保密的向量求和等.但关于保密计算向量等分量数的研究成果还很少,且主要研究向量分量在有全集限制下的两方保密计算问题.主要研究多方参与者隐私向量的等分量数以及相关阈值的安全计算问题.首先针对向量设计了分量-矩阵编码方法,结合ElGamal门限加密系统,构造了多方向量等分量数保密计算协议.进一步以向量等分量数保密计算协议为基础,研究设计了多方向量等分量数阈值问题保密计算协议.所有向量分量没有全集的限制.应用模拟范例方法对文中所有协议的安全性进行了严格证明.效率分析和实验验证表明设计的协议是简单高效的.最后,将所设计的协议应用于解决一些实际安全计算问题.     

恶意模型下的最大(小)值保密计算

安全多方计算是国际密码学界研究的热点,计算一组数据的最大(小)值问题是一个基本的计算问题,保密计算最大(小)值是安全多方计算的一个基础问题,在电子商务、保密招投标、保密数据挖掘等方面有广泛的应用,还可以作为基本模块用于构造更多的安全多方计算协议如各种保密优化协议、保密推荐协议、保密选优协议.目前这个问题的解决方案都只能抵抗被动攻击,尚没有见到能够抵抗主动攻击的解决方案.抵抗被动攻击的解决方案只能提供最基本的安全保障,在有可能遭受主动攻击的实际应用场景中无法保证安全.抵抗主动攻击的解决方案安全性更强,可以为大多实际应用场景提供安全保障,具有重要的理论与实际意义.本文针对保密数据所在范围已知而且范围不太大的应用场景,设计了一种保密数据编码方法,利用这种编码方法构造了抵抗被动攻击的最大(小)值安全多方计算协议,方案非常简单、极易理解,并利用模拟范例证明了协议对于被动攻击是安全的;通过分析协议可能遭受的主动攻击,利用门限解密的密码系统、结合零知识证明和保密洗牌设计阻止或发现主动攻击的措施,把协议改造成能够抵抗主动攻击的安全协议,并用理想-实际范例证明了协议的安全性;分析了方案的效率并通过实验验证了协议的可行性.就我们所知,这是第一个能够抵抗主动攻击的最大(小)值问题解决方案.     

抗主动攻击的保密比较协议

互联网、物联网和大数据的迅速发展,为数据共享带来了无限的机遇,也给私有数据的隐私保护带来了严峻的挑战.安全多方计算是数据共享中隐私保护的关键技术,是密码学的一个重要研究方向,也是国际密码学界研究的热点.保密比较两个数的大小是安全多方计算的一个基本问题,是构建其他隐私保护协议的一个基本模块.当比较的数较小时,还没有可靠的能够抵抗主动攻击的保密比较问题解决方案.很多应用场景中的参与者可能会发动主动攻击,因为尚没有抗主动攻击的保密比较协议,这些场景中的保密比较问题还无法解决.因而研究抗主动攻击的保密比较问题解决方案有重要理论与实际意义.提出了一种加密-选择安全多方计算模式和编码+保密洗牌证明的抵抗主动攻击方法.在此基础上,设计了半诚实模型下安全的保密比较协议,用模拟范例证明了协议的安全性;分析了恶意参与者可能实施的主动攻击,结合ElGamal密码系统的乘法同态性、离散对数与保密洗牌的零知识证明设计阻止恶意行为的措施,将半诚实模型下安全的保密比较协议改造成抗主动攻击的保密比较协议,并用理想-实际范例证明了协议的安全性.最后分析了协议的效率,并通过实验验证协议是可行的.     

保护隐私的有理数科学计算

安全多方计算作为密码学的基本组成部分,是各种密码协议的基础,是国际密码学界的研究热点。近年来,许多学者研究了各种各样的安全多方计算问题,包括保密的信息比较、保密的集合问题和保密的计算几何等,并提出相应的解决方案。而在许多实际应用场景中,安全多方计算问题需要应用有理数进行描述,因此研究有理数域上的安全多方计算问题具有重要的理论与实际意义。但现有的安全多方计算问题的研究成果大多数局限于整数范围,且研究的数据主要是单维度数据。关于有理数域上多维度数据安全多方计算问题的研究较少且无法推广应用。基于有理数的分数表示形式,设计了新的编码方案（有理数编码方案和有理向量编码方案）,可将有理数域上任意维数的数据进行编码,为研究有理数域上其他安全多方计算问题提供了新的解决思路。以该编码方案和单向哈希函数为基础,分别设计了有理数相等、有理向量相等和集合问题的保密判定协议。所设计的协议仅采用基本算术运算和单向哈希函数进行计算,不需要使用公钥加密算法,使得协议的计算效率较高;且协议对研究问题中的数据范围没有限制,适用范围更广。进一步应用模拟范例严格证明了协议在半诚实模型下的安全性;并通过理论分析和模拟实验验证了协议的高效性和适用性。通过具体实例说明协议具有广泛适用性,可以推广应用于其他有理数域的安全多方计算几何问题。     

Efficient solution to the millionaires' problem based on asymmetric commutative encryption scheme

Secure multiparty computation is an important scheme in cryptography and can be applied in various real‐life problems. The first secure multiparty computation problem is the millionaires' problem, and its protocol is an important building block. Because of the less efficiency of public key encryption scheme, most existing solutions based on public key cryptography to this problem are inefficient. Thus, a solution based on the symmetric encryption scheme has been proposed. In this paper, we formally analyse the vulnerability of this solution, and propose a new scheme based on the decisional Diffie‐Hellman assumption. Our solution also uses 0‐encoding and 1‐encoding generated by our modified encoding method to reduce the computation cost. We implement the solution based on symmetric encryption scheme and our protocol. Extensive experiments are conducted to evaluate the efficiency of our solution, and the experimental results show that our solution can be much more efficient and be approximately 8000 times faster than the solution based on symmetric encryption scheme for a 32‐bit input and short‐term security. Moreover, our solution is also more efficient than the state‐of‐the‐art solution without precomputation and can also compare well with the state‐of‐the‐art protocol while the bit length of private inputs is large enough.     

保护隐私的曼哈顿距离计算及其推广应用

安全多方计算是信息时代保护隐私和信息安全的一项关键技术.安全多方科学计算是安全多方计算十分重要的组成部分,目前已经有许多安全多方科学计算问题的解决方案,但还有更多的问题值得人们去研究.关于曼哈顿距离的安全多方计算问题目前研究的结果很少,构造曼哈顿距离的安全计算协议在密码学中有着重要的理论意义,作为基础协议能够广泛应用于其他安全多方计算协议的构造,比如保密计算两点间路径问题,保密判定点与区间以及点与点集的关系问题,以及向量相似度的保密计算都可以归约到曼哈顿距离的安全多方计算问题.本文应用加密选择技巧与一种新的编码方法相结合,以Paillier加密算法为基础,对于不同的情形(无全集限制或有全集限制)设计两数之差绝对值的高效保密计算协议.并以此为基础,设计出两种不同情形下保密计算曼哈顿距离的协议.本文证明了在半诚实模型下这些协议是安全的,并通过模拟实验来测试协议的具体执行时间,理论分析和仿真结果表明本文方案是简单易行的.最后,文中给出实例阐明本文协议在理论以及实际中的广泛应用.     

同态加密方案及安全两点直线计算协议

近年来,安全多方计算一直是密码领域的一个研究热点,保密几何计算是其一个重要分支.过两私有点坐标安全地计算一条直线问题在空间信息安全方面有重要应用前景.本文首先提出一个由加密方计算（或选取）加密底数的Paillier变体同态加密方案,并证明了其在标准模型下对适应性选择明文攻击（adaptive chosen-plaintext attack,CPA）是安全的.然后在半诚实模型下,基于该变体同态加密方案设计了一个能够安全计算过两私有点直线的协议.还可以将此协议推广应用到那些可以归约为安全计算两私有点坐标差商的所有安全多方几何计算问题,从而解决了原有的基于同态加密体制的安全两方计算协议存在的信息泄露问题.     

A Secure Scalar Product Protocol Against Malicious Adversaries

A secure scalar product protocol is a type of specific secure multi-party computation problem.Using this kind of protocol,two involved parties are able to jointly compute the scalar product of their private vectors,but no party will reveal any information about his/her private vector to another one.The secure scalar product protocol is of great importance in many privacy-preserving applications such as privacy-preserving data mining,privacy-preserving cooperative statistical analysis,and privacy-preserving geometry computation.In this paper,we give an efficient and secure scalar product protocol in the presence of malicious adversaries based on two important tools:the proof of knowledge of a discrete logarithm and the verifiable encryption.The security of the new protocol is proved under the standard simulation-based definitions.Compared with the existing schemes,our scheme offers higher efficiency because of avoiding inefficient cut-and-choose proofs.     

一种高效的私有信息检索方案

私有信息检索是一个重要的安全多方计算协议，是指参与查询的用户与数据库拥有者希望在各自的私有信息互不泄露的情况下完成查询操作，该问题在多个情报部门的合作计算领域有着广阔的应用前景．本文将密码学技术应用于预处理辅助随机服务器协议，提出了一个新的私有信息检索解决方案，该方案在保持传统PIR协议通信复杂度不变的情况下，有效地降低了计算复杂度，可以高效应用于文件数据检索．对方案的安全性，计算复杂性和通信复杂性进行了分析．     

Symmetric cryptographic protocols for extended millionaires’ problem

Yao’s millionaires’ problem is a fundamental problem in secure multiparty computation, and its solutions have become building blocks of many secure multiparty computation solutions. Unfortunately, most protocols for millionaires’ problem are constructed based on public cryptography, and thus are inefficient. Furthermore, all protocols are designed to solve the basic millionaires’ problem, that is, to privately determine which of two natural numbers is greater. If the numbers are real, existing solutions do ...     

基于多比特全同态加密的安全多方计算

本文中,我们首先证明了李增鹏等人提出的多比特多密钥全同态加密方案(MFHE)满足密钥同态性质,利用此性质,可以通过门限解密得到最终解密结果.使用该方案,我们设计了一个在CRS模型下和半恶意攻击者模型下安全的三轮多方计算协议(MPC).该安全多方计算协议的安全性是基于容错学习问题(LWE)的两个变种问题Ferr LWE和Some are errorless.LWE,而且,通过非交互的零知识证明,我们可以把半恶意攻击者模型下安全的三轮多方计算协议转变为在恶意模型下安全的三轮多方计算协议.     

基于Goldwasser-Micali加密算法的安全子集计算

针对解决集合间的安全子集问题的协议大多只能保护一个集合元素的隐私进行研究。在半诚实模型下,利用布隆过滤器及Goldwasser-Micali同态加密算法构建了一个安全子集计算协议,并使用安全多方计算中普遍采用的模拟范例证明方法证明了协议的安全性。利用布隆过滤器将拥有大量元素或大数域元素的数据集合映射为较小的数据集合,提升协议的效率及适用范围,同时,借助Goldwasser-Micali同态加密算法保证协议的安全性。相关研究大多是基于二次剩余等困难问题,不可抵抗量子攻击,可抵抗量子攻击的安全子集计算是进一步的研究方向。