保护私有信息的凸多边形相似判定

基于私有信息保护的几何对象间的计算是一个特殊的安全多方计算问题,在很多领域有着重要的应用前景.秘密判定两组数据是否相等、是否对应成比例是安全多方计算的基本问题,在保护私有信息的几何对象间的计算问题方面有着重要意义.通过利用比较相等协议和判断两组数据是否对应成比例的判定协议,解决了凸多边形的相似判定问题,也适用于更一般的多边形相似判定问题,在实际生活中有一定的实用性和可操作性.分析了安全性和复杂性,目前已取得了较好的结果.     

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

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

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

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

一个保护私有信息的线段与椭圆相交判定协议

保护隐私的计算几何是一类特殊的安全多方计算问题。保密路径判定作为一种特殊的保密隐私的几何计算问题,在军事、商业等领域具有重要的应用前景。设计了一个直线与椭圆的位置关系保密判定协议,基于该协议提出了线段与椭圆相交的保密判定协议,并给出协议的正确性、安全性和复杂性的分析。     

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

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

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

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

保护私有信息的范围搜索算法

合作计算的任务可能发生在彼此互不完全信任的各方之间,此时各方参与运算只是想知道最终的结果,而不希望自己的隐私信息被别人获取.安全多方计算所要解决的正是合作计算的隐私保护问题,它能够在保证各方输入的隐私数据安全性的同时获得正确的计算结果.本文考虑学术界一直悬而未决的保护私有信息的范围搜索问题,并且基于安全多方计算的理论和方法实现两类范围搜索协议,同时对它们的安全性、时间复杂性和通讯复杂性进行详细的分析讨论.在本文最后,我们将范围搜索协议应用到保护私有信息的DBSCAN算法中.     

决策树隐私计算研究

为了应对信息时代隐私保护和数据挖掘两方面的要求，提出了一种基于函数秘密共享的决策树隐私计算协议。在机器学习即服务的模型下，服务提供商拥有训练好的决策树模型，用户拥有希望分类的数据，双方都想保护自己的数据不被泄漏。在这个场景下，该协议可以保护决策树的参数、分类数据以及最终分类结果的隐私。使用了基于函数秘密共享的分段函数协议、隐私比较协议、加性秘密共享等安全多方协议，在不影响正确率的情况下实现了隐私保护。     

网格环境中证书和策略的隐私保护机制研究

网格访问控制机制中网格实体的访问控制策略和证书的隐私保护是网格安全的一个重要方面,其重要性随着网格技术的进一步广泛应用而日益突出.利用安全函数计算和同态加密理论来解决访问控制过程中策略和证书的隐私保护问题.首先提出了适应于复合策略表达的电路组成方法,并基于无记忆传递机制和"混乱电路"计算协议提出了策略计算协议;然后提出了基于同态加密理论的属性相等测试协议;最后基于策略计算协议和属性相等测试协议提出了策略和证书的隐私保护协议.分析表明,本方案可以对策略和证书的属性进行完全的隐私保护,并且可以避免传统方法所引起的循环依赖问题.     

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

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

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

安全多方计算是信息时代保护隐私和信息安全的一项关键技术.安全多方科学计算是安全多方计算十分重要的组成部分,目前已经有许多安全多方科学计算问题的解决方案,但还有更多的问题值得人们去研究.关于曼哈顿距离的安全多方计算问题目前研究的结果很少,构造曼哈顿距离的安全计算协议在密码学中有着重要的理论意义,作为基础协议能够广泛应用于其他安全多方计算协议的构造,比如保密计算两点间路径问题,保密判定点与区间以及点与点集的关系问题,以及向量相似度的保密计算都可以归约到曼哈顿距离的安全多方计算问题.本文应用加密选择技巧与一种新的编码方法相结合,以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.     

保护私有信息的两多边形相交面积计算

保护私有信息的计算几何是一类特殊的安全多方计算问题,在军事、商业等领域具有重要的应用前景。在半诚实模型下,利用点线叉积协议设计一个保护私有信息的点包含于多边形判定协议;基于该协议,提出保护私有信息的两多边形相交面积计算协议;分析和证明上述协议的正确性、安全性和复杂性。     

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加密算法的云外包计算下的同态加密方案,在此基础上提出了一个高效,简单的协议,并对协议做了正确性和安全性分析,同时给出了协议计算复杂性和通信复杂性的理论分析与实验验证.最后将保密的字符串排序问题的协议应用于解决百万富翁问题,从根本上解决了大数据情况下的百万富翁问题.     

Shortest polygonal paths in space

A classical problem of geometry is the following: given a convex polygon in the plane, find an inscribed polygon of shortest circumference. In this paper we generalize this problem to arbitrary polygonal paths in space and consider two cases: in the “open” case the wanted path of shortest length can have different start and end point, whereas in the “closed” case these two points must coincide. We show that finding such shortest paths can be reduced to finding a shortest path in a planar “channel”. The latter problem can be solved by an algorithm of linear-time complexity in the open as well in the closed case. Finally, we deal with constrained problems where the wanted path has to fulfill additional properties; in particular, if it has to pass straight through a further point, we show that the length of such a constrained polygonal path is a strictly convex function of some angle α, and we derive an algorithm for determining such constrained polygonal paths efficiently.     

基于连接点的二维多角弧匹配

多角弧匹配问题的关键是，其既能反映多角弧的几何性质，又能反映多角弧拓扑结构的特征选取．在分析了多角弧几何形状的基础上，引入了连接点的概念，并用连接点集表示多角弧，这一表示在旋转和平移变换下是不变的。进一步取该连接点集作为匹配的特征集，给出了特征集之间匹配的算法．该算法是将连接点间的距离积分作为测量函数，使二维多角弧的匹配由连接点的匹配来决定．给出的模拟试验结果表明，该算法效果良好，并且对于数值污染具有健壮性。     

Some techniques for geometric searching with implicit set representations

Summary There are many efficient ways of searching a set when all its elements can be represented in memory. Often, however, the domain of the search is too large to have each element stored separately, and some implicit representation must be used. Whether it is still possible to search efficiently in these conditions is the underlying theme of this paper. We look at several occurrences of this problem in computational geometry and we propose various lines of attack. In the course of doing so, we improve the solutions of several specific problems; for example, computing order statistics, performing polygonal range searching, testing algebraic predicates, etc.