高效的曼哈顿距离保密计算

安全多方计算是密码学领域的热点研究问题之一,文章研究了曼哈顿距离的安全两方计算.曼哈顿距离在许多方面有着重要的理论研究意义和应用价值,比如生物信息学方面.文章基于Paillier同态加密方案,利用绝对值的性质,巧妙地构造了计算整数曼哈顿距离的保密协议,并将其推广到了有理数的范围,设计了一个全新的编码方式,与加密选择技巧...     

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

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

安全排序协议及其应用

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

安全多方计算在空间几何问题中的应用

研究安全多方计算在空间几何问题中的应用,提出了空间中基于阈值的两点之间、点线之间距离关系的保密判定协议,空间中点与两平行平面位置关系的保密判定协议;并利用这些协议作为子协议为空间中基于阈值的点与线段之间距离关系的保密判定问题构造了相应的保密解决方案.所提出的协议和解决方案在工程、商业和军事等领域中具有潜在的应用价值.     

恶意模型下保密点积协议的设计与分析*

保密点积协议是许多安全多方计算问题中一个重要的协议,常被用在许多保密数据挖掘协议中,为这些协议提供了重要的安全保证。目前,一些已存在的保密点积协议至多在半诚实模型下是安全的。基于一些基本的密码学技术设计了一个恶意模型下安全的保密两方共享点积协议,这个协议比以往协议具有更高的安全性。该协议潜在的应用领域是广阔的,如计算Euclidean距离、保密计算几何、保密协作统计分析等。     

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

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

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

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

数轴上保密关系测定协议

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

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

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

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

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

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.     

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

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

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密码系统的乘法同态性、离散对数与保密洗牌的零知识证明设计阻止恶意行为的措施,将半诚实模型下安全的保密比较协议改造成抗主动攻击的保密比较协议,并用理想-实际范例证明了协议的安全性.最后分析了协议的效率,并通过实验验证协议是可行的.     

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

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

Symmetric cryptographic solution to Yao’s millionaires’ problem and an evaluation of secure multiparty computations

Secure multiparty computation has become a central research focus in the international cryptographic community and in the future likely will represent an integral part of computing science. Protocols for Yao’s millionaires’ problem provide the building blocks for many secure multiparty computation protocols, which makes their efficiency critical. Unfortunately, all known protocols for Yao’s millionaires’ problem employ public key cryptography and thus are inefficient. This article constructs a new efficient solution to Yao’s millionaires’ problem based on symmetric cryptography. We first develop an efficient protocol for set-inclusion problems, which has independent interest for secure multiparty computations. The privacy-preserving property of the solution is demonstrated by a well-accepted simulation paradigm. To compare the security levels of different solutions, we propose a new security paradigm that quantitatively captures the security levels of different solutions and can determine which secure multiparty computation solution is preferable. This article thus provides an important supplement to the simulation paradigm. Together with the simulation paradigm, it offers a complete security evaluation benchmark for multiparty computations.