The Research On Privacy-preserving Queries And Matching In Location Based Services

With the development of smart mobile devices and communication techniques,Lo-cation based Services such as Uber and DiDi Chuxing are widely adopted in almost every aspect,which brings great convenience to people’s daily life.Along with the convenience,high privacy concerns are also raised when using these services because users must share their real-time locations with the service providers.The massive data collected by the ser-vice providers will put privacy of users in big risks.On the one hand,service providers may analyze users’data without the authority of users to extract users’mobility patterns and additional private information.On the other hand,users’data may be leaked to regulators or the public under political enforcement or attacks from the internal or the external.Thus,users are unable to enjoy the convenience of location-based services unless their privacy is well protected.However,due to the shortcomings on strength of privacy-preserving and accuracy,traditional obfuscation-based location privacy-preserving schemes cannot meet the requirements of security and QoS of nowadays locations-based services.To tackle this challenge,this dissertation focuses on the protection of queries’privacy in two common location-based services(range search and ride-matching)and propose several schemes to preserve users’query privacy under different statuses of target location data sets.The main contributions of our work are summarized as follows:To support range search over encrypted numerical data,we propose an efficient and generalized geometric range search scheme for encrypted spatial location data.The scheme allows the service provider to find data points within the given geometric range over encrypted spatial location data.To ensure the privacy of queries,the scheme ex-tends Asymmetric Scalar-product Preserving Encryption(ASPE)with dynamic geometric transformation,which enhances the security by dynamically transforming the data points in both the data set and the queried geometric range simultaneously.Besides,the scheme supports indexing over encrypted spatial data,which achieves sub-linear search efficiency.Formal security analysis and experiments demonstrate that the proposed scheme is secure under known-background model and achieves high search accuracy and efficiency.To protect location privacy of users in Online-Ride-Hailing service,we proposed pRide,a privacy-preserving ride-matching scheme that allows the service provider to match a rider with its nearest driver in road networks without revealing the locations of both the driver and driver.Compared with existing privacy-preserving ride-matching schemes,pRide achieves much higher matching accuracy by using road network distance.Besides,pRide also achieves relative high matching efficiency due to novel usage of road network embedding technique.Moreover,the core of pRide is a privacy-preserving way to find the nearest neighbor in road networks,which may be of independent interest for applications in other fields such as task matching in mobile crowdsourcing.Considering the locations of drivers may be public in practice,we further propose Pri-vateRide,a private ride request scheme which allows the service provider to match riders and drivers over public information of the drivers and private ride requests of the riders.To do that,PrivateRide resolves to hardware-enforced Trusted Execution Environment,and proposed an efficient ride-matching algorithm utilizing hub-based labeling technique,which supports efficient ride-matching with basic security guarantee.To further defend against side-channel attacks,we make the ride-matching algorithm data-oblivious by aug-menting it with oblivious label accessing and oblivious distance computation.Compared with existing private request schemes on public location data,PrivateRide achieves much higher matching accuracy and privacy guarantee of data-obliviousness with acceptable matching efficiency for practice.Different from Online-Ride-Hailing service,drivers in ridesharing service have their own planned trips and share vacant seats with riders who have similar or identical trips.To protect location privacy of riders and drivers in ridesharing,we proposed P~2Ride,a privacy-preserving ride-matching scheme.P~2Ride allows the ridesharing platform to match drivers with appropriate riders according to their respective encrypted planned trips and encrypted ride requests.To do that,P~2Ride first convert the complex ride-matching computation into equality testing by proposing a matching testing method based on over-lapping partition techniques.Then,P~2Ride obtains a secure and efficient ride-matching scheme by designing a novel non-interactive private equality testing protocol.Compared with existing privacy-preserving schemes for ridesharing,P~2Ride significantly reduces in-teractions between riders/drivers and the ridesharing platform,and relieves the user ends from heavy computation and communication burden.