Secure Euclidean distance computation in presence of malicious adversaries

Abstract

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

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

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

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，杨波2. 恶意模型下计算欧几里德距离的协议[J]. 计算机工程与应用, 2015, 51(24): 109-113.

[1]	DAI Qi, LI Min, LIU Yang, LI Lihong. Fast Attribute Reduction Algorithm Based on Fuzzy Hierarchical Quotient Space [J]. Computer Engineering and Applications, 2021, 57(4): 55-60.
[2]	FAN Jianping, CHENG Rui, WU Meiqin. Distance Measure of Interval-Valued Complex Fuzzy Soft Sets and Its Application [J]. Computer Engineering and Applications, 2020, 56(9): 248-259.
[3]	WANG Zilong, LI Jin, SONG Yafei. Improved K-means Algorithm Based on Distance and Weight [J]. Computer Engineering and Applications, 2020, 56(23): 87-94.
[4]	LI Kang1, YANG Yudong2. Image Segmentation Algorithm Based on Improved Chan-Vese Model and Edge Transformation [J]. Computer Engineering and Applications, 2019, 55(6): 204-208.
[5]	LIU Yudong, WANG Xu’an, GAO Zhongshi. Euclidean Distance Outsourcing Computation Protocol Based on Homomorphic Encryption Algorithm [J]. Computer Engineering and Applications, 2019, 55(15): 110-116.
[6]	YAN Xuelong, CHEN Zhuo. Analog Circuit Fault Prognostic Utilizing Particle Swarm Optimized Multi-Kernel Relevance Vector Machine [J]. Computer Engineering and Applications, 2019, 55(12): 140-144.
[7]	FENG Wenbin1, LIU Baohua2. Research on image matching based on improved SIFT algorithm [J]. Computer Engineering and Applications, 2018, 54(3): 200-205.
[8]	LI Zhilei, CHENG Yongqiang, JIA Haoli. Photoshop subjective examination questions marking method based on image contrast [J]. Computer Engineering and Applications, 2018, 54(23): 150-155.
[9]	WANG Wenhui1, YANG Geng1, GE Wei1, LIU Peidong2, QIAN Chen3. Fuzzy C-Means clustering algorithm under noise uneven condition and its application [J]. Computer Engineering and Applications, 2018, 54(19): 172-178.
[10]	FAN Qingfu, ZHANG Lei, LIU Leijun, BAO Suning, FANG Chen. Online GPS trajectory data compression based on offset calculation [J]. Computer Engineering and Applications, 2017, 53(8): 254-259.
[11]	ZHOU Ketao, LIU Weiguo, SHI Ronghua. K-degree anonymity scheme for preserving privacy based on similarity of neighborhood degree sequence [J]. Computer Engineering and Applications, 2017, 53(19): 102-108.
[12]	PEI Jingdong, WANG Wenhu, WANG Shu, CHENG Langyong. Elliptical leading edge fitting strategy of elementary blade profile [J]. Computer Engineering and Applications, 2015, 51(3): 243-246.
[13]	ZHANG Yankai1, BAO Fang2, WANG Shitong1. Protection-type transfer learning clustering algorithm with cosine distance metric [J]. Computer Engineering and Applications, 2015, 51(23): 131-138.
[14]	WU Jie1, REN Jiangtao2. Two level palmprint recognition algorithm based on subspace features [J]. Computer Engineering and Applications, 2015, 51(11): 175-178.
[15]	ZHOU Wenqin1，2, ZHANG Yechi1，2, SHI Runhua1，2. Anonymous authentication scheme based on secure multiparty computation [J]. Computer Engineering and Applications, 2014, 50(24): 81-85.

Secure Euclidean distance computation in presence of malicious adversaries

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics