安全向量优势协议及其应用

Secure Vector Dominance Protocol and Its Applications

百万富翁问题是安全多方计算研究的热点问题之一,也是其他安全多方计算协议的基本构成模块.安全向量优势统计问题是百万富翁问题的推广,用于两方在不泄漏自己保密向量信息的前提下统计出满足大于关系的分量的数目.本文基于同态加密算法,通过对保密的数据进行编码,设计了一个计算百万富翁问题的协议,并利用模拟范例对协议进行安全性证明.然后利用这个新的协议作为基本模块,设计了一个向量优势统计协议,通过效率分析显示我们的方案是简单、高效的.最后将向量优势统计协议应用到整除判定问题和点与若干直线关系判定问题.

The millionaires＇ problem is an important problem in secure multiparty computation and a basic building block of secure multiparty computation protocols. Secure vector dominance statistic problem is a problem generalized for the millionaires＇problem, which can be used to get the number of yi 〉 xi without leaking further information. In this paper, we first propose an encoding scheme to encode private numbers; then based the new encoding scheme and homomorphic encryption scheme, we design a protocol for millionaires＇problem and prove that the protocol is secure in the semi-honest model using the simulation paradigm. Then, we utilize this scheme to propose a solution to secure vector dominance statistic problem. The performance analysis indicates that our protocol is simpler and more efficient than the others. Finally, we use the scheme to solve the integer division problem and privately determine the relation between point and lines.