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

于海宁; 张宏莉; 余翔湛; 曲家兴; 葛蒙蒙

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

您当前的位置：

首页 >

文章列表页 >

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

学术论文 | 更新时间：2024-06-05

- 隐私保护的轨迹相似度计算方法
- Privacy-preserving trajectory similarity computation method
- 通信学报 2022年43卷第11期页码：1-13
- 作者机构：
  
  1. 哈尔滨工业大学网络空间安全学院，黑龙江哈尔滨 150001
  2. 黑龙江省网络空间研究中心，黑龙江哈尔滨 150001
  3. 南洋理工大学计算机科学与工程学院，新加坡 639798
- 作者简介：
  
  [ "于海宁（1983− ），男，黑龙江萝北人，博士，哈尔滨工业大学副研究员、硕士生导师，主要研究方向为数据安全、隐私计算、应用密码学等" ]
  [ "张宏莉（1973− ），女，吉林榆树人，博士，哈尔滨工业大学教授、博士生导师，主要研究方向为网络与信息安全、网络测量与建模、网络计算、并行处理等" ]
  [ "余翔湛（1973− ），男，黑龙江哈尔滨人，博士，哈尔滨工业大学教授、博士生导师，主要研究方向为信息安全、网络流量分析等" ]
  [ "曲家兴（1979− ），男，黑龙江哈尔滨人，博士，黑龙江省网络空间研究中心教授级高级工程师，主要研究方向为网络安全、网络舆情分析等" ]
  [ "葛蒙蒙（1994− ），男，安徽亳州人，南洋理工大学博士生，主要研究方向为加密网络流量行为表征、加密网络应用识别、加密网页流量分类和网络流量入侵检测等" ]
- 基金信息：
  
  国家自然科学基金资助项目(62172123);国家自然科学基金资助项目(61732022);黑龙江省自然科学基金资助项目(YQ2021F007);中央引导地方科技发展专项资金资助项目(ZY20B11)
- DOI：10.11959/j.issn.1000-436x.2022223
  中图分类号： TP39
- 网络首发：2022-11，
  
  纸质出版：2022-11-25
- 稿件说明：
移动端阅览
于海宁, 张宏莉, 余翔湛, 等. 隐私保护的轨迹相似度计算方法[J]. 通信学报, 2022,43(11):1-13.

Haining YU, Hongli ZHANG, Xiangzhan YU, et al. Privacy-preserving trajectory similarity computation method[J]. Journal on Communications, 2022, 43(11): 1-13.
于海宁, 张宏莉, 余翔湛, 等. 隐私保护的轨迹相似度计算方法[J]. 通信学报, 2022,43(11):1-13. DOI： 10.11959/j.issn.1000-436x.2022223.

Haining YU, Hongli ZHANG, Xiangzhan YU, et al. Privacy-preserving trajectory similarity computation method[J]. Journal on Communications, 2022, 43(11): 1-13. DOI： 10.11959/j.issn.1000-436x.2022223.

摘要

为解决轨迹外包服务中轨迹相似度计算的隐私泄露问题，提出了一种隐私保护的轨迹相似度计算（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.

关键词

Keywords

references

许佳捷 , 郑凯 , 池明旻 , 等 . 轨迹大数据:数据、应用与技术现状 [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 .

SHAN Z H , REN K , BLANTON M , et al . Practical secure computation outsourcing [J ] . ACM Computing Surveys , 2019 , 51 ( 2 ): 1 - 40 .

李凤华 , 李晖 , 贾焰 , 等 . 隐私计算研究范畴及发展趋势 [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 .

万盛 , 李凤华 , 牛犇 , 等 . 位置隐私保护技术研究进展 [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 .

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 .

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.

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

SMART N P , VERCAUTEREN F . Fully homomorphic SIMD operations [J ] . Designs,Codes and Cryptography , 2014 , 71 ( 1 ): 57 - 81 .

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 .

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 .

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.

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 .

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 .

许华杰 , 吴青华 , 胡小明 . 基于轨迹多特性的隐私保护算法 [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 .

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 .

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 .

浏览量

780

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

面向深度学习的高效安全推理研究综述

基于同态密文转换的隐私保护卷积神经网络推理方案

基于同态加密的高效安全联邦学习聚合框架

支持同态算术运算的数据加密方案算法研究

基于稀疏矩阵变换和有界随机扰动的K-Means聚类外包方案