曼哈顿距离的保密计算

Abstract

曼哈顿距离的安全多方计算是一个新的安全多方计算问题, 在保密科学计算、保密信息过滤、生物信息学保密计算等方面具有重要的理论意义与应用价值. 保密计算两点间的曼哈顿距离首先需要保密计算两个数的绝对值, 此问题未见研究报道; 其次需要在不知道两个数的前提下, 保密计算两个数的和. 本文用新的方法解决曼哈顿距离的安全多方计算问题, 设计了两种不同的编码方法, 结合同态加密算法, 可以将绝对值的计算分别转化为保密计算两向量的海明距离与保密计算两向量的内积. 双方可直接得到两点间的曼哈顿距离, 避免了分别计算横纵坐标差的绝对值之和导致的信息泄露. 同时, 利用数字承诺的思想, 使得双方在关键环节具有平等地位, 公平地得到最后结果, 避免了拥有私钥一方过早得到结果导致的欺骗行为. 使用模拟范例证明了协议是安全的. 理论分析和实验显示, 本方案可以高效安全地计算两点间的曼哈顿距离.

Alternate abstract:

The SMC (secure multiparty computation) of Manhattan distance is a totally new SMC problem, which has important theoretical significance and broad applications in secure scientific computing, information filtering, bioinformatics, etc. Privately computing the Manhattan distance between two points needs to privately compute the absolute values of two numbers, of which no solution has been found yet. Then it needs to privately compute the sum of two absolute values without revealing the two unknown values. This study proposed new methods to solve this problem. Firstly, by designing two different coding methods and the use of homomorphic encryption algorithm, the computation of absolute values can be converted into privately computing the Hamming distance and inner product between two vectors. After computation, the Manhattan distance can be obtained directly without revealing any information. Meanwhile, the idea of digital commitment is used so that two participants have equal statuses in key steps and the result is fair. The cheating of the participant with private key can be avoided because of obtaining the result untimely. The security of the protocol is proved by using the simulation paradigm. Finally, the theoretical and experimental results shows that the proposed schemes can compute the Manhattan distance between two points efficiently and securely.