Euclidean Distance Outsourcing Computation Protocol Based on Homomorphic Encryption Algorithm

doi:10.3778/j.issn.1002-8331.1901-0209

Computer Engineering and Applications ›› 2019, Vol. 55 ›› Issue (15): 110-116.DOI: 10.3778/j.issn.1002-8331.1901-0209

Previous Articles Next Articles

Euclidean Distance Outsourcing Computation Protocol Based on Homomorphic Encryption Algorithm

LIU Yudong, WANG Xu’an, GAO Zhongshi

1.Key Laboratory for Network and Information Security of Chinese Armed Police Force, Engineering University of Chinese Armed Police Force, Xi’an 710086, China
2.Institute of Cryptology Engineering, Engineering University of the Chinese Armed Police Force, Xi’an 710086, China

Online:2019-08-01 Published:2019-07-26

基于同态加密算法的欧氏距离外包计算协议

柳玉东，王绪安，高忠石

1.武警工程大学网络与信息安全武警部队重点实验室，西安 710086
2.武警工程大学密码工程学院，西安 710086

Abstract

Abstract: In order to solve the problem of Euclidean distance computation in the ciphertext state of the outsourced storage data, an Euclidean distance outsourcing computing protocol is constructed to reduce the burden of users and protect data privacy. The crypto-distributed two trapdoors public-key cryptosystem is reviewed. And then a secure multiplication protocol, the perfect square trinomial protocol under a single key and joint public key are proposed respectively based on the homomorphic encryption algorithm. Based on these three basic computing protocols, the outsourcing computation protocol of Euclidean distance is designed. Security analysis and efficiency analysis show that the protocol is sufficiently secure and efficient. The protocol solves the problem of outsourcing calculation related to Euclidean distance well and has certain promotion effect on the development of image processing.

Key words: homomorphic encryption, Euclidean distance, data outsourcing, perfect square trinomial, computing protocol

摘要： 针对外包存储数据在密文状态下有关欧氏距离无法计算的问题，构建了欧氏距离外包计算协议，降低了用户的计算负担，保护了数据隐私。回顾了分布式双陷门公钥密码方案。基于同态加密算法设计了安全的乘法协议、单个密钥加密下的完全平方式协议和联合公钥加密下的完全平方式协议，基于这三个基础计算协议设计了欧氏距离的外包计算协议。安全性分析表明该协议足够安全，效率分析显示该协议较为高效，并较好地解决了有关欧氏距离的外包计算问题，对于图像处理的发展有一定的促进作用。

关键词: 同态加密, 欧氏距离, 数据外包, 完全平方式, 计算协议

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.

柳玉东，王绪安，高忠石. 基于同态加密算法的欧氏距离外包计算协议[J]. 计算机工程与应用, 2019, 55(15): 110-116.

[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]	WEI Lifei, LI Mengsi, ZHANG Lei, CHEN Congcong, CHEN Yujiao, WANG Qin. Privacy-Preserving Linear Regression Algorithm Based on Secure Two-Party Computation [J]. Computer Engineering and Applications, 2021, 57(22): 139-146.
[3]	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.
[4]	SONG Xiuli, ZHOU Daoyang, CAO Yunfan. Design and Simulation of [d]dimensional Quantum Homomorphic Encryption Algorithm [J]. Computer Engineering and Applications, 2020, 56(7): 109-115.
[5]	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.
[6]	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.
[7]	TAN Yuesheng, LU Liming, WANG Jingyu. Ciphertext-Policy Attribute Encryption Scheme Based on Homomorphic Encryption [J]. Computer Engineering and Applications, 2019, 55(19): 115-120.
[8]	ZHANG Sijia1, GU Chunhua2, WEN Mi1. Analysis and Research on Data Aggregation Scheme in Smart Grid [J]. Computer Engineering and Applications, 2019, 55(12): 83-89.
[9]	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.
[10]	FENG Wenbin1, LIU Baohua2. Research on image matching based on improved SIFT algorithm [J]. Computer Engineering and Applications, 2018, 54(3): 200-205.
[11]	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.
[12]	XIANG Guangli, LI Ankang, LIN Xiang, XIONG Bin. Multiple keywords retrieval scheme based on homomorphic encryption [J]. Computer Engineering and Applications, 2018, 54(2): 97-101.
[13]	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.
[14]	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.
[15]	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.

Euclidean Distance Outsourcing Computation Protocol Based on Homomorphic Encryption Algorithm

基于同态加密算法的欧氏距离外包计算协议

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics