Privacy-preserving trajectory similarity computation method - Haining YU; Hongli ZHANG; Xiangzhan YU; Jiaxing QU; Mengmeng GE (Tongxin xuebao)
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.