Research On Secure Trajectory Search Scheme Of Encrypted Trajectory Database

With the development of GPS technology and the popularity of locationbased services,various clients generate a large amount of trajectory data,which is stored in the cloud to save local storage space and realize data sharing.Massive trajectory data provides rich data support for online ride,travel route recommendation,public transportation planning and other services.However,trajectory data records users’ private information such as daily dynamics,behavioral preferences and commuting routes.Trajectory retrieval is one of the important means to realize the value of trajectories.Due to the differences in application scenarios and information importance,trajectory retrieval has different security requirements and retrieval types.The research of encrypted trajectory database mainly focuses on ride matching service and computation of trajectory similarity.However,when the trajectory similarity measurement is inconsistent with the actual traffic flow,the retrieval results are not accurate.Single trajectory recommendation can not explore the value of massive trajectories,and the diversity of recommendation results is poor and trajectory resources are wasted.When trajectory retrieval is carried out on various types of trajectory databases,the cost of computation is high and the efficiency of search is low due to the exhaustion and aggregation point distance.In this paper,the above problems are studied respectively,and the main innovations are as follows:1.The online ride matching scheme DSRide,with matching results consistent with the actual traffic flow,is designed to protect location privacy.Existing researches of ride matching over the road network without traffic flow direction and traffic restriction,have a large error between the calculated distance and the actual distance,and a low accuracy of matching result.In this paper,a dynamic road network model is constructed,and a travel consumption algorithm on dynamic road network is proposed.On this basis,a scheme of accurate ride matching on dynamic road network is designed,in which partitioning and expanding is utilized to realize the preliminary screening of users,while ensuring the accurate matching of users at the edge of road network block.The location obscuring technology in the algorithm ensures the difference of the ciphertext with the same user and the same location,and avoids the attackers’guessing of the users’ locations.A variant of the PPTR algorithm adapted with the algorithm protects the users’ locations and supports one-to-many riding match.In addition,a scheme,DSRiden,based on noise adding technology is proposed to meet the higher security requirements.Scheme DSRide can effectively improve the matching efficiency.The accuracy of matching result is 95%.DSRiden can ensure the confidentiality of user requirements.2.A joint route recommendation method on multi-source encrypted trajectory,eJMTiE,is proposed.The existing researches of trajectory recommendation realize single trajectory matching,but lack the measurement method and the search method of joint trajectories and secure aggregation mechanism of distances.So they cannot provide the route transfer recommendation on the multi-source encrypted trajectory database.In this paper,the similarity of oneto-many trajectories and the definition of joint trajectory search are formally given,and the joint multi-trajectory search algorithm in encrypted trajectory database is proposed to increase the diversity of trajectory recommendation.Specifically,a heuristic trajectory search algorithm,JMT,is designed,in which the information of the visited trajectories and trajectory points are used to eliminate the trajectories those do not meet the search requirements and to reduce the number of checking trajectory points.The expanded joint trajectory search algorithm,e-JMT,is designed to reduce the redundancy caused by the large search range.In this paper,the algorithm of secure distance computing and the algorithm of secure XOR are used to compute the joint-trajectory similarity and to verify the linkablility of trajectory points.While protecting trajectory and linkablility of trajectory points,eJMTiE realizes efficient joint-trajectory search in trajectory database.It can significantly reduce the time of search and realize the semantic security of encrypted trajectory data.3.A public transport route planning scheme without leaking the location of the route is designed.The existing public transport route planning schemes only support plain-text retrieval.Because they lack the method of constructing index,and the strategy of space pruning and data screening on multi-type encrypted trajectory database,they cannot be directly used for public transport route planning on cipher text.However,the reverse point query on cipher text only returns a single point,which cannot realize the aggregation and comparison of distances.In this scheme,a hybrid index eRBFtree is constructed on the encrypted commuting data base and encrypted trajectory data base.eRBFtree supports database partitioning and fast k nearest neighbor query.In this paper,strategies of spatial pruning and data screening are proposes to realize efficient reverse nearest neighbor trajectory retrieval on the encrypted trajectory database.In this scheme,CKKS is used to compute and aggregate trajectory similarity securely.Firstly,the nearest neighbor trajectory points are used as the anchor points to prune the commuter data space to obtain the candidate commuter data.Then,the similarity between the candidate commuter data and the nearest neighbor trajectories are used to refine the candidate commuter data.Finally,the k nearest neighbor trajectories are find for every refined commuter data.Experiments on real data show that this scheme can retrieve and return the service objects of the planned route safely and efficiently.