Privacy-preserving trajectory similarity computation method

Haining YU; Hongli ZHANG; Xiangzhan YU; Jiaxing QU; Mengmeng GE

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

您当前的位置：

首页 >

文章列表页 >

Privacy-preserving trajectory similarity computation method

Papers | 更新时间：2024-06-05

- Privacy-preserving trajectory similarity computation method
- Journal on Communications Vol. 43, Issue 11, Pages: 1-13(2022)
- 作者机构：
  
  1. 哈尔滨工业大学网络空间安全学院，黑龙江哈尔滨 150001
  2. 黑龙江省网络空间研究中心，黑龙江哈尔滨 150001
  3. 南洋理工大学计算机科学与工程学院，新加坡 639798
- 作者简介：
- 基金信息：
  
  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)
- DOI：10.11959/j.issn.1000-436x.2022223
  CLC： TP39
- Online First：2022-11，
  
  Published：25 November 2022
- 稿件说明：
移动端阅览
Haining YU, Hongli ZHANG, Xiangzhan YU, et al. Privacy-preserving trajectory similarity computation method[J]. Journal on Communications, 2022, 43(11): 1-13.
DOI：

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 .

Views

937

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Survey of research on efficient secure inference for deep learning

Privacy-preserving convolutional neural network inference scheme based on homomorphic ciphertext transformation

Efficient secure federated learning aggregation framework based on homomorphic encryption

Research on algorithms of data encryption scheme that supports homomorphic arithmetical operations

K-Means clustering outsourcing scheme based on sparse matrix transformation and bounded random perturbation

Related Author

HU Peng

SUN Lei

HU Cuiyun

GUO Song

WANG Jingwen

WANG Zhihong

YAO Jingyi

LI Ruiqi

Related Institution

Department of Cryptogram Engineering, Information Engineering University

Troops of PLA

Henan Key Laboratory of Information Security

College of Safety Science and Technology and Engineering, Civil Aviation University of China

College of Cyber Science, Nankai University

AI问答

⁰