恶意模型下计算欧几里德距离的协议

Secure Euclidean distance computation in presence of malicious adversaries

安全多方计算(MPC)是一个允许多个参与方在保持各自输入隐私的前提下联合计算一个函数。Yao和Goldreich等人(STOC’87)开创性的工作表明,存在陷门置换的前提下,任何一个函数都存在安全多方计算协议,并给出了安全多方计算的一个通用解决方案,但是该方案由于效率问题而不实用。因此,Goldreich同时指出需要针对特定问题提出特定的安全多方计算协议。提出了一个新的基于分布式EI Gamal加密的计算两个向量欧几里德距离的安全协议,并在混合模型下给出了协议的安全性证明。与原来的方案比较,该协议的计算和通信复杂度都较低,适用于计算和通信能力都有限的应用环境。

Secure Multiparty Computation（MPC）deals with protocols that allow a group of agents to jointly compute a function of their individual private inputs. Nothing is revealed except the value of function in the end. Even though Yao and Goldreich et al.（STOC＇87）have already proposed the general solution of any function, the general MPC has been proven to be inefficient and impractical. It is necessary to construct special MPC protocol for special problem. In this paper,a new scheme which can evaluate the Euclidean distance between two vectors is proposed. This scheme is based on distributed EI Gamal encryption, and is proven secure in the hybrid model. Compared with the previous schemes, this scheme has lower computation and communication complexity. It can be suitable to the circumstances which are computation and communication limited.