隐私保护的轨迹相似度计算方法

doi:10.11959/j.issn.1000-436x.2022223

通信学报 ›› 2022, Vol. 43 ›› Issue (11): 1-13.doi: 10.11959/j.issn.1000-436x.2022223

• 学术论文 • 下一篇

隐私保护的轨迹相似度计算方法

于海宁¹, 张宏莉¹, 余翔湛¹, 曲家兴², 葛蒙蒙¹^,³

¹ 哈尔滨工业大学网络空间安全学院，黑龙江哈尔滨 150001
² 黑龙江省网络空间研究中心，黑龙江哈尔滨 150001
³ 南洋理工大学计算机科学与工程学院，新加坡 639798

修回日期:2022-07-12 出版日期:2022-11-25 发布日期:2022-11-01
作者简介:于海宁（1983− ），男，黑龙江萝北人，博士，哈尔滨工业大学副研究员、硕士生导师，主要研究方向为数据安全、隐私计算、应用密码学等
张宏莉（1973− ），女，吉林榆树人，博士，哈尔滨工业大学教授、博士生导师，主要研究方向为网络与信息安全、网络测量与建模、网络计算、并行处理等
余翔湛（1973− ），男，黑龙江哈尔滨人，博士，哈尔滨工业大学教授、博士生导师，主要研究方向为信息安全、网络流量分析等
曲家兴（1979− ），男，黑龙江哈尔滨人，博士，黑龙江省网络空间研究中心教授级高级工程师，主要研究方向为网络安全、网络舆情分析等
葛蒙蒙（1994− ），男，安徽亳州人，南洋理工大学博士生，主要研究方向为加密网络流量行为表征、加密网络应用识别、加密网页流量分类和网络流量入侵检测等
基金资助:
国家自然科学基金资助项目(62172123);国家自然科学基金资助项目(61732022);黑龙江省自然科学基金资助项目(YQ2021F007);中央引导地方科技发展专项资金资助项目(ZY20B11)

Privacy-preserving trajectory similarity computation method

Haining YU¹, Hongli ZHANG¹, Xiangzhan YU¹, Jiaxing QU², Mengmeng GE¹^,³

¹ School of Cyberspace Science, Harbin Institute of Technology, Harbin 150001, China
² Heilongjiang Province Cyberspace Research Center, Harbin 150001, China
³ School of Computer Science and Engineering, Nangyang Technological University, Singapore 639798

Revised:2022-07-12 Online:2022-11-25 Published:2022-11-01
Supported by:
The National Natural Science Foundation of China(62172123);The National Natural Science Foundation of China(61732022);Heilongjiang Provincial Natural Science Foundation of China(YQ2021F007);The Special Projects for the Central Government to Guide the Development of Local Science and Technology(ZY20B11)

摘要/Abstract

摘要：

为解决轨迹外包服务中轨迹相似度计算的隐私泄露问题，提出了一种隐私保护的轨迹相似度计算（pTSC）方法，在该方法中轨迹服务存储来自轨迹拥有者的加密轨迹，接收来自轨迹查询者的加密兴趣轨迹，并支持基于加密的兴趣轨迹和存储轨迹的相似度安全计算，进而避免拥有者的存储轨迹和查询者的兴趣轨迹泄露。为高效地计算密态轨迹的相似度，提出了一个基于最长公共子序列的轨迹相似度安全计算协议，该协议利用类同态加密算法和安全比较协议实现了密态轨迹的最长公共子序列的高效计算。此外，设计了一种密文压缩算法，进一步提升效率。理论分析和实验评估证明了pTSC方法的安全性和高效性。

关键词: 隐私保护, 轨迹相似度, 同态加密, 安全计算

Abstract:

To tackle privacy concerns on user information leakage in trajectory outsourcing services, a privacy-preserving trajectory similarity computation (pTSC) method was proposed.A trajectory outsourcing service provider was enabled to store encrypted trajectories from owners, wait for encrypted interested trajectories from requesters, and compute trajectory similarity between an interested trajectory and stored trajectories in ciphertext domain without learning anything about users’ trajectories.To compute a trajectory similarity over encrypted trajectories efficiently, a secure trajectory similarity computation protocol with longest common subsequence was proposed, which used somewhat homomorphic encryption and secure comparison protocol to compute the length of longest common subsequence over two encrypted trajectories.Furthermore, a ciphertext compression algorithm was designed to improve efficiency.Theoretical analysis and experimental evaluations show that pTSC method is secure and efficient.

Key words: privacy-preserving, trajectory similarity, homomorphic encryption, secure computing

中图分类号:

TP39

于海宁, 张宏莉, 余翔湛, 曲家兴, 葛蒙蒙. 隐私保护的轨迹相似度计算方法[J]. 通信学报, 2022, 43(11): 1-13.

Haining YU, Hongli ZHANG, Xiangzhan YU, Jiaxing QU, Mengmeng GE. Privacy-preserving trajectory similarity computation method[J]. Journal on Communications, 2022, 43(11): 1-13.

图/表 9

图1

图2

图3

图4

表1

图5

图6

图7

图8

参考文献 23

[1]	许佳捷, 郑凯, 池明旻 ,等. 轨迹大数据:数据、应用与技术现状[J]. 通信学报, 2015,36(12): 97-105.
	XU J J , ZHENG K , CHI M M ,et al. Trajectory big data:data,applications and techniques[J]. Journal on Communications, 2015,36(12): 97-105.
[2]	SHAN Z H , REN K , BLANTON M ,et al. Practical secure computation outsourcing[J]. ACM Computing Surveys, 2019,51(2): 1-40.
[3]	李凤华, 李晖, 贾焰 ,等. 隐私计算研究范畴及发展趋势[J]. 通信学报, 2016,37(4): 1-11.
	LI F H , LI H , JIA Y ,et al. Privacy computing:concept,connotation and its research trend[J]. Journal on Communications, 2016,37(4): 1-11.
[4]	万盛, 李凤华, 牛犇 ,等. 位置隐私保护技术研究进展[J]. 通信学报, 2016,37(12): 124-141.
	WAN S , LI F H , NIU B ,et al. Research progress on location privacy-preserving techniques[J]. Journal on Communications, 2016,37(12): 124-141.
[5]	PAILLIER P , . Public-key cryptosystems based on composite degree residuosity classes[C]// Proceedings of International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 1999: 223-238.
[6]	HUANG Y , EVANS D , K J ,et al. Faster secure {two-party} computation using garbled circuits[C]// Proceedings of 20th USENIX Security Symposium. Berkeley:USENIX Association, 2011:35.
[7]	FREEDMAN M J , NISSIM K , PINKAS B . Efficient private matching and set intersection[C]// Proceedings of International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 2004: 1-19.
[8]	HALLGREN P , ORLANDI C , SABELFELD A . PrivatePool:privacy-preserving ridesharing[C]// Proceedings of IEEE 30th Computer Security Foundations Symposium. Piscataway:IEEE Press, 2017: 276-291.
[9]	PAGNIN E , GUNNARSSON G , TALEBI P ,et al. TOPPool:time-aware optimized privacy-preserving ridesharing[J]. Proceedings on Privacy Enhancing Technologies, 2019,2019(4): 93-111.
[10]	A?VODJI U M , HUGUENIN K , HUGUET M J ,et al. SRide:a privacy-preserving ridesharing system[C]// Proceedings of the 11th ACM Conference on Security ＆ Privacy in Wireless and Mobile Networks. New York:ACM Press, 2018: 40-50.
[11]	LIU A , ZHENGY K , LIZ L ,et al. Efficient secure similarity computation on encrypted trajectory data[C]// Proceedings of IEEE 31st International Conference on Data Engineering. Piscataway:IEEE Press, 2015: 66-77.
[12]	SU H , LIU S C , ZHENG B L ,et al. A survey of trajectory distance measures and performance evaluation[J]. The VLDB Journal, 2020,29(1): 3-32.
[13]	CHEON J H , KIM A , KIM M ,et al. Homomorphic encryption for arithmetic of approximate numbers[C]// Proceedings of International Conference on the Theory and Application of Cryptology and Information Security. Berlin:Springer, 2017: 409-437.
[14]	LYUBASHEVSKY V , PEIKERT C , REGEV O . On ideal lattices and learning with errors over rings[J]. Journal of the ACM, 2013,60(6): 1-35.
[15]	SMART N P , VERCAUTEREN F . Fully homomorphic SIMD operations[J]. Designs,Codes and Cryptography, 2014,71(1): 57-81.
[16]	QI Y N , ATALLAH M J . Efficient privacy-preserving k-nearest neighbor search[C]// Proceedings of The 28th International Conference on Distributed Computing Systems. Piscataway:IEEE Press, 2008: 311-319.
[17]	HE Y Y , NI J B , WANG X Y ,et al. Privacy-preserving partner selection for ride-sharing services[J]. IEEE Transactions on Vehicular Technology, 2018,67(7): 5994-6005.
[18]	NARAYANAN A , THIAGARAJAN N , LAKHANI M ,et al. Location privacy via private proximity testing[C]// Proceedings of Network and Distributed System Security. Piscataway:IEEE Press, 2011:11.
[19]	SALDAMLI G , CHOW R , JIN HX ,et al. Private proximity testing with an untrusted server[C]// Proceedings of the sixth ACM Conference on Security and Privacy in Wireless and Mobile Networks. NewYork:ACM Press, 2013: 113-118.
[20]	ZHU H , MENG X , KOLLIOS G . Privacy preserving similarity evaluation of time series data[C]// Proceedings of Extending Database Technology. Berlin:Springer, 2014: 499-510.
[21]	许华杰, 吴青华, 胡小明 . 基于轨迹多特性的隐私保护算法[J]. 计算机科学, 2019,46(1): 190-195.
	XU H J , WU Q H , HU X M . Privacy protection algorithm based on multi-characteristics of trajectory[J]. Computer Science, 2019,46(1): 190-195.
[22]	TENG Y P , SHI Z , ZHAO F Y ,et al. Signature-based secure trajectory similarity search[C]// Proceedings of IEEE 20th International Conference on Trust,Security and Privacy in Computing and Communications. Piscataway:IEEE Press, 2021: 196-206.
[23]	TENG Y P , ZHAO F Y , LIU J ,et al. SeTS3:a secure trajectory similarity search system[C]// Proceedings of Database Systems for Advanced Applications. Cham:Springer International Publishing, 2022: 522-526.

多项式模度	加密时间/ms	解密时间/ms	同态加法时间/ms	同态乘法时间/ms	同态旋转时间/ms	密文尺寸/KB
1 024	0.159	0.007	0.002	0.016	—	16.6
2 048	0.293	0.013	0.004	0.031	—	33.056
4 096	1.224	0.045	0.011	0.108	0.656	65.936
8 192	3.209	0.147	0.037	0.380	2.871	394.865
16 384	11.05	0.583	0.140	1.485	16.761	789.617

隐私保护的轨迹相似度计算方法

Privacy-preserving trajectory similarity computation method

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 9

参考文献 23

相关文章 15

Metrics

推荐阅读 0

[1]	马鑫迪, 李清华, 姜奇, 马卓, 高胜, 田有亮, 马建峰. 面向Non-IID数据的拜占庭鲁棒联邦学习[J]. 通信学报, 2023, 44(6): 138-153.
[2]	冯涛, 陈李秋, 方君丽, 石建明. 基于本地化差分隐私和属性基可搜索加密的区块链数据共享方案[J]. 通信学报, 2023, 44(5): 224-233.
[3]	夏莹杰, 朱思雨, 刘雪娇. 区块链架构下具有条件隐私的车辆编队跨信任域高效群组认证研究[J]. 通信学报, 2023, 44(4): 111-123.
[4]	胡柏吉, 张晓娟, 李元诚, 赖荣鑫. 支持多功能的V2G网络隐私保护数据聚合方案[J]. 通信学报, 2023, 44(4): 187-200.
[5]	徐明, 张保俊, 伍益明, 应晨铎, 郑宁. 面向网络攻击和隐私保护的多智能体系统分布式共识算法[J]. 通信学报, 2023, 44(3): 117-127.
[6]	余晟兴, 陈钟. 基于同态加密的高效安全联邦学习聚合框架[J]. 通信学报, 2023, 44(1): 14-28.
[7]	杨亚涛, 刘德莉, 刘培鹤, 曾萍, 肖嵩. BFV-Blockchainvoting：支持BFV全同态加密的区块链电子投票系统[J]. 通信学报, 2022, 43(9): 100-111.
[8]	张学旺, 黎志鸿, 林金朝. 基于公平盲签名和分级加密的联盟链隐私保护方案[J]. 通信学报, 2022, 43(8): 131-141.
[9]	王继锋, 王国峰. 边缘计算模式下密文搜索与共享技术研究[J]. 通信学报, 2022, 43(4): 227-238.
[10]	封化民, 史瑞, 袁峰, 李艳俊, 杨旸. 高效的强隐私保护和可转让的属性票据方案[J]. 通信学报, 2022, 43(3): 63-75.
[11]	彭滔, 钟文韬, 王国军, 罗恩韬, 熊金波, 刘忆宁, Hao Wang. 移动社交网络中面向隐私保护的精确好友匹配[J]. 通信学报, 2022, 43(11): 90-103.
[12]	史瑞, 封化民, 谢惠琴, 史国振, 刘飚, 杨旸. 基于带智能卡的移动终端实现的隐私保护的属性票据方案[J]. 通信学报, 2022, 43(10): 26-41.
[13]	熊金波, 周永洁, 毕仁万, 万良, 田有亮. 边缘协同的轻量级隐私保护分类框架[J]. 通信学报, 2022, 43(1): 127-137.
[14]	晏燕, 丛一鸣, Adnan Mahmood, 盛权政. 基于深度学习的位置大数据统计发布与隐私保护方法[J]. 通信学报, 2022, 43(1): 203-216.
[15]	马立川, 彭佳怡, 裴庆祺, 朱浩瑾. 高效的决策树隐私分类服务协议[J]. 通信学报, 2021, 42(8): 80-89.