高效安全向量计算及其推广

安全多方计算是密码学的一个重要研究方向,也是目前国际密码学界的研究热点.因为许多实际问题都可以用向量来描述,研究向量的保密计算具有重要的理论与实际意义.目前,关于向量保密计算问题大多是在整数集上进行研究,关于有理数向量问题的研究很少.在此主要研究有理数域上向量的安全多方计算问题,包括向量点积、向量相等、向量优势等问题,设计了安全高效的计算协议,扩大了向量保密计算的应用范围.对这些协议的安全性分析和效率分析表明,它们在安全性和效率方面与现有协议相比具有明显优势.并且利用所设计的协议解决了一些新的向量问题和计算几何问题.     

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

随着信息技术的快速发展, 在保护数据隐私的条件下进行多方合作计算变得越来越普及, 安全多方计算已经成为解决这类保密计算问题的核心技术. 向量的保密计算是安全多方计算的重要研究方向, 目前有很多研究成果, 包括保密计算向量的点积, 保密的向量求和等. 但关于保密计算向量等分量数的研究成果还很少, 且主要研究向量分量在有全...     

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

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

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

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

数轴上保密关系测定协议

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

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

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

安全排序协议及其应用

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

点和区间包含问题的保密计算

安全多方计算问题是近年来密码学研究的热点问题,其中多方保密计算是网络空间隐私保护与信息安全的关键技术。文章研究了计算几何中有理数域内点和区间包含问题的保密计算问题,即保密的判定一个隐私的有理数是否属于一个保密的有理区间。文章利用安全多方计算的思想设计了一个高效的安全协议,并证明了协议在半诚实模型下的安全性,与现有的其他文献相比,本文的协议具有更低的计算复杂度。     

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

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

基于阈值的点线距离与位置关系保密判定协议

特殊安全多方计算问题是近几年国际密码学界一个研究热点。保密计算几何问题就是其中之一,它是指两个或多个互不信任的参与方希望利用他们私有的几何信息作为输入协作解决某一计算几何问题,同时他们想要确保没有把自己的任何私有输入信息泄露给其他参与方,除了规定的输出。设计了基于阈值的两点之间、点线之间距离关系的保密判定协议,点与两平行直线位置关系的保密判定协议,使用这几个协议构造了基于阈值的点与线段之间距离关系的保密判定协议。这些协议在工程、商业和军事等领域中有着潜在的应用前景。     

Comparing two sets without disclosing them

Secure multiparty computation has become a central research focus in the international cryptographic community. Secure comparing two sets is an important problem in secure multiparty computation. The research on privately determining whether two sets are equal has not been investigated. This study solves the problem by mapping these sets into natural numbers and then comparing correspond- ing numbers, We propose two secure multiparty computation protocols for comparing two sets. It is proved by well-accepted simulation paradigm that these solutions are private in semi-honest model. These solutions have important significance in constructing other secure multiparty computation protocols.     

云环境下集合隐私计算

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

A novel quantum scheme for secure two-party distance computation

Secure multiparty computational geometry is an essential field of secure multiparty computation, which computes a computation geometric problem without revealing any private information of each party. Secure two-party distance computation is a primitive of secure multiparty computational geometry, which computes the distance between two points without revealing each point’s location information (i.e., coordinate). Secure two-party distance computation has potential applications with high secure requirements in military, business, engineering and so on. In this paper, we present a quantum solution to secure two-party distance computation by subtly using quantum private query. Compared to the classical related protocols, our quantum protocol can ensure higher security and better privacy protection because of the physical principle of quantum mechanics.     

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 ...     

基于字符串排序的高效保密数据库查询

安全多方计算是近年来国际密码学界研究的热点问题之一,是信息社会隐私保护的核心技术.保密地将字符串按照字典序排序问题是一个全新的安全多方计算问题,在信息安全领域有重要的实际意义和广泛的应用前景.它不仅可以提高保密数据库查询的效率,还可以解决大数据情况下的百万富翁问题.为了保密地判断两个字符串按照字典序排序的位置关系,本文首先设计了一种新的编码方法和一种基于ElGamal加密算法的云外包计算下的同态加密方案,在此基础上提出了一个高效,简单的协议,并对协议做了正确性和安全性分析,同时给出了协议计算复杂性和通信复杂性的理论分析与实验验证.最后将保密的字符串排序问题的协议应用于解决百万富翁问题,从根本上解决了大数据情况下的百万富翁问题.     

集合交集元素之和的保密计算

安全多方计算是国际密码学的研究热点之一，保密计算集合交集元素之和问题是安全多方计算比较新的问题之一.该问题在工商业、医疗健康等领域具有重要的理论意义和实用价值.现有解决方案是在有全集情况下设计的，在计算过程中会泄露交集的势且存在一定的误判.在半诚实模型下基于Paillier同态加密算法设计了3个协议，协议1计算共有标识符的数量（即用户标识符交集的势）以及与这些用户相关联的整数值之和，协议2和协议3是在不泄露交集势的情况下计算交集元素关联值之和.整个计算过程不泄露关于协议双方私人输入的任何更多信息.所提协议是在无全集情况下设计的，采用模拟范例证明了所设计协议的安全性，用实验验证协议的高效性.