Ride-Hailing Service (RHS) has drawn plenty of attention as it provides transportation convenience for riders and financial incentives for drivers. Despite these benefits, riders risk the exposure of sensitive location data during ride requesting to an untrusted Ride-Hailing Service Provider (RHSP). Our motivation arises from repetitive matching, i.e., the same driver is repetitively assigned to the same rider. Meanwhile, we introduce a driver exclusion function to protect riders' location privacy. Existing work on privacy-preserving RHS overlooks this function. While Secure k Nearest Neighbor (SkNN) facilitates efficient matching, the state-of-the-art neglects a collusion attack. To solve this problem, we formally define repetitive matching and strong location privacy, and propose Mnemosyne: privacy-preserving ride matching with collusion-resistant driver exclusion. We extend the simple integration of equality checking and item exclusion to a dynamic integration. We concatenate each prefix of an acceptable identity range to each location code when generating a ride request, i.e., secure mix index. We process each prefix of the driver identity to generate a ride response, i.e., a mix token. We build an indistinguishable Bloom-filter as an index to query the token. When matching riders with drivers, the colluding parties cannot distinguish identity prefixes from location codes. We build a prototype of Mnemosyne based on servers, smartphones, and a real-world dataset. Experimental results demonstrate that Mnemosyne outperforms existing work regarding strong location privacy and computational costs.@en

Location-Based Services (LBSs) depend on a Service Provider (SP) to store data owners’ geospatial data and to process data users’ queries. For example, a Yelp user queries the SP to retrieve the k nearest Starbucks by submitting her/his current location. It is well-acknowledged that location privacy is vital to users and several prominent Secure k Nearest Neighbor (SkNN) query processing schemes are proposed. We observe that no prior work addresses the requirement of repetitive query after index update and its privacy issue, i.e., how to match a data item from the cloud repetitively in an oblivious and unlinkable manner. Meanwhile, a malicious SP may skip some data items and recommend others due to unfair competition. In this work, we formally define the repetitive query and its privacy objectives and present an Repetitive, Oblivious, and Unlinkable SkNN scheme ROU. Specifically, we design a multi-level structure to organize locations to further improve search efficiency. Second, we integrate data item identity into the framework of existing SkNN query processing. Data owners encrypt their data item identity and location information into a secure index, and data users encrypt a customized identity range of a previously retrieved data item and location information into a token. Next, the SP uses the token to query the secure index to find the specific data item via privacy-preserving range querying. We formally prove the privacy of ROU in the random oracle model. We build a prototype based on a server to evaluate the performance with a real-world dataset. Experimental results show that ROU is efficient and practical in terms of computational cost, communication overhead, and result verification.@en

Shortest distance queries over large-scale graphs bring great benefits to various applications, i.e., save planning time and travelling expenses. To protect the sensitive nodes and edges in the graph, a user outsources an encrypted graph to an untrusted server without losing the query ability. However, no prior work has considered the user requirement of the shortest path with k unsorted nodes. In particular, we are concerned with how to securely find the shortest path by passing k nodes that do not have a fixed traverse order. To solve the problems, we propose Gespun (stands for Graph encryption for shortest path queries with k unordered nodes). It includes an oracle encryption scheme that is provably secure against the semi-honest server. Specifically, we compute the shortest paths and distances for all nodes locally to obtain path-distance oracles. We transform the shortest paths to a sequence of secure codes by using a pseudo-random permutation to protect the structure privacy. We encrypt the shortest distance by using additively homomorphic encryption. Second, we pack the oracles in link-list nodes and store them in an array-based dictionary after another permutation. Next, we construct a search graph to compute the shortest path while guaranteeing that the path passes the required k nodes. We formally prove that Gespun is adaptively semantically-secure in the random oracle. We implement a prototype of Gespun and evaluate its performance. Experiments results demonstrate that Gespun is efficient, e.g., a query over 6301 nodes, 20777 edges, and 5 unsorted nodes only needs 483 ms to get queried results. We believe that our research problem span new research that soon promotes a new line of graph encryption schemes.@en

Outsourcing data users' location data to a cloud server (CS) enables them to obtain kk nearest points of interest. However, data users' privacy concerns hinder the wide-scale use. Several studies have achieved Secure k Nearest Neighbor (SkNN) query, but do not address time-restricted access or result privacy, and randomly partition data items which degrades efficiency. In this article, we propose Time-restricted, verifiable, and efficient Query Processing (TiveQP). TiveQP has three distinguishing features. 1) Expand SkNN: data users can query kk nearest locations open at a specific time. 2) Adopt a stronger threat model: we assume the CS is malicious and propose complementary set (i.e., transform proving 'in' a set to proving 'in' its complementary set) to allow data users to verify results without leaking unqueried data items' information. 3) Improve efficiency: we design a space encoding technique and a pruning strategy to improve efficiency in query processing and result verification. We formally proved the security of TiveQP in the random oracle model. We conducted extensive evaluations over a Yelp dataset to show that TiveQP significantly improves over existing work, e.g., top-10NN query over 100 thousand data items only needs 10 ms to get queried results and 1.4 ms for verification.@en