一种高效的百万富翁问题协议及其应用

百万富翁问题是安全多方计算的基础问题,但现有解决方案计算复杂度高且效率较低,在两数相等时无法进行精确比较.针对该问题,提出一种基于0-1编码的百万富翁问题协议.使用改进的0-1保密数据编码规则构建向量,利用ElGamal同态加密变体算法的同态性质,将百万富翁问题转化为向量中两元素求和的问题,同时在半诚实模型下利用模拟范...

An Efficient Protocol for Millionaires'Problem and Its Application

The existing solutions to the Millionaires’ Problem(MP),a basic problem in Secure Multi-Party Computation(SMC),have high computational complexity and low efficiency,and the two numbers can not be compared accurately when they are equal.To solve the problems,this paper proposes a protocol for MP based on 0-1 coding.The improved 0-1 secret data coding rule is used to construct the vector.By using the homomorphic property of the ElGamal homomorphic encryption variant algorithm,the MP is transformed into the sum of two elements in the vector.In the semi-honest model,the simulation examples are used to prove the correctness and security of the protocol,and the protocol is applied to solving the number of intersection sets of two secure parties.Experimental results show that compared with the protocols using ElGamal and Paillier homomorphic encryption algorithms,the proposed protocol has lower computational complexity and higher efficiency,and the two numbers can be compared accurately when they are equal.