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

计算机工程与应用 ›› 2015, Vol. 51 ›› Issue (24): 109-113.

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

杨得新1，刘力铭1，杨波2

1.广州城市职业学院信息技术系，广州 510405
2.陕西师范大学计算机科学学院，西安 710062

出版日期:2015-12-15 发布日期:2015-12-30

Secure Euclidean distance computation in presence of malicious adversaries

YANG Dexin1, LIU Liming1, YANG Bo2

1.Department of Information Technology, Guangzhou City Polytechnic, Guangzhou 510405, China
2.School of Computer Science, Shaanxi Normal University, Xi’an 710062, China

Online:2015-12-15 Published:2015-12-30

摘要/Abstract

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

关键词: 安全多方计算, 欧几里德距离, 分布式EI Gamal加密

Abstract: 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.

Key words: secure multiparty computation, Euclidean distance, distributed EI Gamal encryption

杨得新1，刘力铭1，杨波2. 恶意模型下计算欧几里德距离的协议[J]. 计算机工程与应用, 2015, 51(24): 109-113.

YANG Dexin1, LIU Liming1, YANG Bo2. Secure Euclidean distance computation in presence of malicious adversaries[J]. Computer Engineering and Applications, 2015, 51(24): 109-113.

[1]	夏超1，仲红1，2，石润华1，2. 基于同态加密技术的安全多方乘积协议[J]. 计算机工程与应用, 2015, 51(1): 76-80.
[2]	傅天裕1，2，罗永龙1，2，郭良敏1，2，孙玲玲1，2. 保护私有信息的两多边形相交面积计算[J]. 计算机工程与应用, 2014, 50(9): 37-40.
[3]	吴芬1，仲红1，2，石润华1，2. 隐私保护的费马问题极值计算协议[J]. 计算机工程与应用, 2014, 50(4): 77-80.
[4]	周文钦1，2，张也弛1，2，石润华1，2. 基于安全多方计算的匿名认证方案[J]. 计算机工程与应用, 2014, 50(24): 81-85.
[5]	吴涛1，黄莉静2. 一种改进的系统间隐私保持协同过滤推荐算法[J]. 计算机工程与应用, 2013, 49(15): 80-83.
[6]	孙培勇，刘忆宁，李亚军. 一种公开可验证的安全电子彩票协议[J]. 计算机工程与应用, 2013, 49(13): 68-70.
[7]	孙玲玲1，2，罗永龙1，2，郭良敏1，2，孙丽萍1，2. 一种基于声誉的评分累积信任模型[J]. 计算机工程与应用, 2012, 48(27): 69-73.
[8]	仲红^1,2，孙彦飞²，燕飞飞²，黄宏升². 保护私有信息的空间最近点对协议[J]. 计算机工程与应用, 2011, 47(4): 87-89.
[9]	李禾¹，王述洋². 关于除法的安全双方计算协议[J]. 计算机工程与应用, 2010, 46(6): 86-88.
[10]	符祖峰¹，罗文俊²，童玲¹. 一个保护私有信息的线段与椭圆相交判定协议[J]. 计算机工程与应用, 2010, 46(17): 77-80.
[11]	张彩云，罗永龙，石磊. 关于安全判定点和区间包含关系的解决方法[J]. 计算机工程与应用, 2010, 46(17): 107-109.
[12]	王珽，罗文俊. 基于阈值的点线距离与位置关系保密判定协议[J]. 计算机工程与应用, 2010, 46(13): 87-89.
[13]	逯绍锋^1，2，罗永龙^1，2，3. 保护私有信息的符号距离判定协议[J]. 计算机工程与应用, 2009, 45(33): 77-80.
[14]	张春生¹,姚绍文²,王世普². 一个M+1电子拍卖方案的密码学分析[J]. 计算机工程与应用, 2009, 45(11): 111-113.
[15]	逯绍锋^1,2,罗永龙^1,2. Graham算法求解凸包问题中的隐私保护[J]. 计算机工程与应用, 2008, 44(36): 130-133.