不同坐标系下空间两球体关系的安全判定协议

如何将处于不同空间坐标系下的几何对象统一到相同空间坐标系下是合作过程中经常遇到的问题,为了保证双方安全与利益,合作双方都希望不泄露自身的私有输入信息。针对以上情况,首先提出并设计了隐私保护的不同空间坐标系下的两点距离计算协议,然后进一步设计了保护隐私的不同空间坐标系下两球体关系的判定协议,分析了协议的正确性、安全性和复杂性。在保护参与方私有输入信息的条件下,所设计的协议解决了不同空间坐标系下球体与球体之间的相对位置安全判定问题。     

一个点与矩形区域包含关系的安全判定协议

点与矩形区域包含关系的安全判定是指两个用户基于各自的输入信息,共同完成矩形区域是否包含点的判定,并且双方都不能获得对方的输入信息,该问题是一个安全两方计算问题,广泛应用于竟标、拍卖等不泄露信息的商业领域.通过对点与矩形区域位置关系的分析,得到一个判定点与矩形区域位置的公式,然后基于点积协议设计了一个点与矩形区域包含关系的安全判定协议,并且分析了协议的正确性、安全性和复杂性.在保护用户私有输入信息的条件下,解决了点与矩形区域的位置关系判定问题.     

基于不同坐标系的点球关系安全判定协议

基于隐私保护的不同坐标系下的点球关系判定是计算几何中的一类基本问题,针对该问题进行了研究并提出一种新的解决方案.在点积协议基础上设计了一种点球关系判定协议,使得双方均在不透露自己任何信息的情况下,能够完成坐标系的转换,并判定点是否包含在球体内,分析了该判定协议的正确性、安全性和复杂性.最后提出可以使用该协议来解决一类与此相似的几何对象关系的判定问题.     

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

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

空间几何对象相对位置判定中的私有信息保护

保护私有信息的计算几何是一类特殊的安全多方计算问题，它是指在一个互不信任的多用户网络中，几个用户基于各自输入的几何信息共同协作来完成某项可靠的计算任务，但任何一个用户都不愿意向其他用户暴露自己的输入，该问题在协作进行太空开发等领域有着重要的应用前案．秘密判定两组数据是否对应成比例是安全多方计算的一个基本问题，在判定空间几何对象相对位置关系中起着重要作用．设计了判断两组数据是否对应成比例的秘密判定协议；分析了该协议的正确性、安全性及复杂性；在保护用户私有输入信息的条件下，解决了空间中点、直线、平面等几何对象之间的相对位置判定问题．     

空间几何对象相对位置的新安全判定方法

针对空间几何对象相对位置判定问题提出一种新的解决方案,也就是运用矩阵秩的概念和一般矩阵求和的安全两方计算协议秘密判定空间几何对象相对位置问题.关于此问题,之前罗永龙教授设计了对应成比例判定协议,而文中则利用矩阵秩的概念和一般矩阵求和的安全两方计算协议设计了一些基础的空间几何对象相对位置安全判定协议.运用此协议解决了空间中的平面与平面位置关系问题、平面与直线位置关系问题和直线与直线位置关系问题.提出的新安全判定方法不久解决了空间几何对象相对位置判定问题,也将在其他安全多方计算问题中起到重要作用.     

隐私保护的不同坐标系两点距离计算

坐标系变换是合作完成某项测绘作业过程中经常遇到的问题,但因为关系到自身的安全与利益,合作双方都不希望泄露各自的输入信息.首次提出保护私有信息的坐标系变换问题,同时设计了相应的变换协议,并以此协议为基础,进一步设计了不同坐标系下两点距离计算协议,分析了两协议的正确性、安全性及复杂性.在保护私有信息的条件下,解决了不同坐标...     

隐私保护的点与多边形位置关系判定协议

隐私保护的计算几何是安全多方计算的一个全新研究领域。针对已有的安全判定点与多边形位置关系协议 的缺陷,在半诚实模型下,提出基于铅垂线算法和不经意传输协议的隐私保护的点与多边形位置关系判定协议,并对 该协议的正确性、计算复杂性、通信复杂性和安全性进行了分析和证明。新的协议不仅可以在实数域中使用,不局限 于凸多边形,而且能适用于多边形带孔的情况。     

隐私保护的两方几何圆位置关系判定

两圆间的位置关系判定问题是常见的几何计算问题之一.在保护两方各自输入圆信息的条件下,本文设计了一个隐私保护的两方几何圆位置关系判定方案,以实现在半诚实模型下安全地求解两圆间五种位置关系.本文运用Paillier同态加密技术实现了圆心间欧几里德距离的保密计算,通过将Paillier明文空间划分为两等长区间以实现解密结果在明文空间中正确映射的方法,提出隐私保护的欧几里德距离计算协议.此外,基于该协议我们设计了一个隐私保护的两圆间位置关系判定协议,在未泄露两圆半径与圆心等敏感信息的前提下提高了两方的计算效率.本文给出了方案具体的设计步骤、详细的安全性分析和实际的性能测试.实验结果表明,在两圆相距较近和相距较远的情况下判定两圆相离、外切、相交、内切和内含五种位置关系时,本方案均适用.同时,我们的方案具有计算复杂度不高及通信开销低等优势.     

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

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

Secure Two-Party Point-Circle Inclusion Problem

Privacy-preserving computational geometry is a special secure multi-party computation and has many applications. Previous protocols for determining whether a point is inside a circle are not secure enough. We present a two-round protocol for computing the distance between two private points and develop a more efficient protocol for the point-circle inclusion problem based on the distance protocol. In comparison with previous solutions, our protocol not only is more secure but also reduces the number of communication rounds and the number of modular multiplications significantly.     

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

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

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

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

安全排序协议及其应用

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

公平理性委托计算协议

已存在的安全计算集合关系的协议大多基于公钥加密算法,因此很难再嵌入到带有属性关系的公钥加密或密文搜索中.针对该问题,本文给出了非加密方法安全计算集合包含关系和集合交集的2个协议.我们首先利用（n,n）秘密共享的思想分别将原来2个问题转化为集合相等问题.在此基础上,结合离散对数,构造了安全计算集合包含关系的协议1和集合交集的协议2.最后的分析显示：我们的方案没有使用任何公钥加密方法,在保持了较优通信复杂性的同时,便于作为一种子模块嵌入到带有集合操作关系的公钥加密体制或者密文搜索体制中,从而丰富这些方案的功能.     

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

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

关于安全判定点和区间包含关系的解决方法

点和区间包含关系的安全判定是指两个用户基于各自的输入信息,共同完成区间是否包含点的判定,并且双方都不能获得对方的输入信息,该问题是一个安全两方计算问题,其在军事、商业领域有着重要的应用前景。分别基于比较和同态加密方案设计了两个点和区间包含关系的安全判定协议,并且分析了协议的正确性、安全性和复杂性。     

Secure Two-Party Computational Geometry

Secure Multi-party Computation has been a research focus in international cryptographic community in recent years. In this paper the authors investigate how some computational geometric problems could be solved in a cooperative environment, where two parties need to solve a geometric problem based on their joint data, but neither wants to disclose its private data to the other party. These problems are the distance between two private points, the relation between a private point and a circle area, the relation between a private point and an ellipse area and the shortest distance between two point sets. The paper gives solutions to these specific geometric problems, and in doing so a building block is developed, the protocol for the distance between two private points, that is also useful in the solutions to other geometric problems and combinatorial problems.