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

Privacy-preserving trajectory similarity computation method

作　　者：于海宁[1] 张宏莉[1] 余翔湛[1] 曲家兴 葛蒙蒙 YU Haining;ZHANG Hongli;YU Xiangzhan;QU Jiaxing;GE Mengmeng(School of Cyberspace Science,Harbin Institute of Technology,Harbin 150001;China 2.Heilongjiang Province Cyberspace Research Center,Harbin 150001;China 3.School of Computer Science and Engineering,Nangyang Technological University,Singapore 639798)

机构地区：[1]哈尔滨工业大学网络空间安全学院,黑龙江哈尔滨150001 [2]黑龙江省网络空间研究中心,黑龙江哈尔滨150001 [3]南洋理工大学计算机科学与工程学院,新加坡639798

出　　处：《通信学报》2022年第11期1-13,共13页Journal on Communications

基　　金：国家自然科学基金资助项目(No.62172123,No.61732022);黑龙江省自然科学基金资助项目(No.YQ2021F007);中央引导地方科技发展专项资金资助项目(No.ZY20B11)。

摘　　要：为解决轨迹外包服务中轨迹相似度计算的隐私泄露问题,提出了一种隐私保护的轨迹相似度计算(pTSC)方法,在该方法中轨迹服务存储来自轨迹拥有者的加密轨迹,接收来自轨迹查询者的加密兴趣轨迹,并支持基于加密的兴趣轨迹和存储轨迹的相似度安全计算,进而避免拥有者的存储轨迹和查询者的兴趣轨迹泄露。为高效地计算密态轨迹的相似度,提出了一个基于最长公共子序列的轨迹相似度安全计算协议,该协议利用类同态加密算法和安全比较协议实现了密态轨迹的最长公共子序列的高效计算。此外,设计了一种密文压缩算法,进一步提升效率。理论分析和实验评估证明了pTSC方法的安全性和高效性。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 trajecto-ry 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 experi-mental evaluations show that pTSC method is secure and efficient.

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

分 类 号：TP39[自动化与计算机技术—计算机应用技术]