保护隐私的计算几何问题研究

发布时间：2018-04-18 21:32

本文选题：安全多方计算 + 计算几何　；参考：《西安科技大学》2017年硕士论文

【摘要】：安全多方计算(Secure Multi-party Computation,SMC)是指在一个互相不信任的计算环境中,n个参与者利用各自的私有信息共同计算一个函数。计算结束后,每一方都能得到正确的结果,并且每一方除了自己的输入和输出外,不能得到其它方的任何数据。保护隐私的分布式计算都归结于此,比如:统计分析、比较相等、科学计算、计算几何、数据挖掘等。本文主要围绕保密计算几何中的两类问题:几何问题和集合问题,进行了研究。首先,针对几何问题,研究了如何保护隐私的判断空间位置关系。已存方案大多是通过转化为距离或数据对应成比例问题解决的,计算复杂性较高、应用范围受限且为计算性安全。针对这些问题,本文先将原问题转化为一个点是否为一个方程的解,再利用一种简单高效的内积协议一次性解决了点线、点面、线线、线面、面面等5种空间位置关系的判定。本文方案没有利用任何公钥加密算法,取得了信息论安全。其次,针对集合问题,研究了如何保护隐私的判断集合成员关系和如何计算集合交集的势。已存方案大多是通过转化为多次元素匹配查找、多次加密与多次调用内积协议的问题来解决,计算繁琐,效率低。针对这两个问题,本文首先设计了一种新的0-1编码,然后结合同态加密解决了集合成员判定问题。其次,又设计了其他两种新的编码:0-R编码与1-0编码,并分别结合同态加密、置换协议和内积协议给出了解决集合交集势的两种方法。其中一种方法没有利用任何公钥加密算法,取得了信息论安全。最后,本文对所有协议的正确性、安全性和复杂性进行了理论分析,证明本文设计的协议是高效安全的,且具有实际意义。
[Abstract]:Secure Multi-party Computing (SMC) means that in a computing environment with mutual distrust, n participants use their private information to calculate a function together.After the calculation, each side can get the correct results, and each side can not get any data except their own input and output.The privacy of distributed computing is attributed to this, such as: statistical analysis, comparative equality, scientific computing, computational geometry, data mining and so on.This paper focuses on two kinds of problems in the geometry of secure computing: geometric problem and set problem.First of all, we study how to protect privacy to judge the spatial position relation for geometric problems.Most of the existing schemes are solved by transforming them into distance or data proportional problems, which have high computational complexity, limited application scope and computational security.In order to solve these problems, this paper first transforms the original problem into the solution of whether a point is an equation or not, and then uses a simple and efficient inner product protocol to determine the spatial position relationship of point line, point surface, line line, line surface and surface.This scheme does not use any public key encryption algorithm, and obtains information theory security.Secondly, for the set problem, we study how to protect the privacy of the set membership and how to calculate the potential of the set intersection.Most of the existing schemes are solved by transforming them into multiple element matching searching, multiple encryption and multiple calls to the inner product protocol. The calculation is tedious and the efficiency is low.In order to solve these two problems, a new 0-1 encoding is designed, and then the problem of judging set members is solved with homomorphic encryption.Secondly, we design two new codes: 0-R code and 1-0 code, and give two methods to solve the set intersection potential by combining homomorphic encryption, permutation protocol and inner product protocol, respectively.One of the methods does not use any public key encryption algorithm to obtain information theory security.Finally, the correctness, security and complexity of all the protocols are analyzed theoretically, which proves that the protocol designed in this paper is efficient and secure, and has practical significance.
【学位授予单位】：西安科技大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP309;O18

【参考文献】