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

Secure Manhattan Distance Computation and Its Application

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

Secure multiparty computation,also called privacy-preserving computation,is a key technology of privacy protecting and information security in the information age.Secure multiparty computation uses many cryptographic primitives,such as public key cryptosystems,secret sharing,oblivious transfer,bit commitment,one way hash function,garbled circuit,zero-knowledge proof to solve various cryptographic problems.Secure multiparty computation protocols are called general cryptographic protocols,and have many practical applications in scientific computation,data-mining,computational geometry,commerce and statistical analysis,etc.It is a focus of the international cryptographic community in recent years.Since it was introduced by Yao,it has been extensively studied.The fruit of secure multiparty computation is rich.Secure multiparty scientific computation is an important part of secure multiparty computation.Though many secure multiparty scientific computation problems have been studied,but the solutions of many addressed problems are not satisfactory and need to be improved or to explore better solutions.There are also various problems that still need to be studied.Secure Manhattan distance computation is such a problem that needs to be studied.Different from Euclidean distance,Manhattan distance between two points in an Euclidean space with fixed Cartesian coordinate system is defined as the sum of the lengths of the projections of the line segment between the points onto the coordinate axes.It is a reasonable distance measure.Private Manhattan distance computation has wide applications in practice.It has important theoretical and practical significance in cryptography to design protocol to privately compute the Manhattan distance,because the protocol can be used as a building block to solve many other secure multiparty computation problems such as privately computing the path between two private points,privately determining the relationship between a private point and a private interval,privately determining the relationship between a private point and a private point set and privately computing the similarity between two vectors.At present,there are few research results on Manhattan distance secure computation.We address this problem in this paper.To privately compute the Manhattan distance between two private points,we first design a new encoding scheme.This encoding scheme encodes a private number into a private array which makes private absolute value computation easy.Then we use the Paillier cryptosystem,the encoding scheme,and encrypt-and-choose technique to design a protocol to privately compute the absolute value of the difference of two private numbers.Using the protocol for absolute value problem as a building block,we further design a protocol to privately compute the Manhattan distance between two private points.We design protocols for two different scenarios:one for the scenario where the domain of the private data is known and fairly small;another for the scenario where the domain of the private data is unknown.We prove that these protocols are secure in the semi-honest model.We analyze and test the efficiency of our protocols.Theoretical analysis and simulation show that our protocols are efficient.Finally,we show how to use our protocol to solve other secure multiparty computation problems,such as the secure vector similarity computation and the secure determination of the relationship between a vector and a vector set.