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

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

Digital forensics is crucial to fight crimes around the world. Decentralized Digital Forensics (DDF) promotes it to another level by channeling the power of blockchain into digital investigations. In this work, we focus on the privacy and security of DDF. Our motivations arise from (1) how to track an anonymous- and-malicious data user who leaks only a part of the previously requested data, (2) how to achieve access control while protecting data from untrusted data centers, and (3) how to enable efficient and secure search on the blockchain. To address these issues, we propose Themis: an anonymous and secure DDF scheme with traceable anonymity, private access control, and efficient search. Our framework is boosted by establishing a Trusted Execution Environment in each authority (blockchain node) for securing the uploading, requesting, and searching. To instantiate the framework, we design a secure and robust watermarking scheme in conjunction with decentralized anonymous authentication, a private and fine-grained access control scheme, and an efficient and secure search scheme based on a dynamically updated data structure. We formally define and prove the privacy and security of Themis. We build a prototype with Ethereum and Intel SGX2 to evaluate its performance, which supports processing data from a considerable number of data providers and investigators.@en

Digital forensics is crucial to fight crimes around the world. Decentralized Digital Forensics (DDF) promotes it to another level by channeling the power of blockchain into digital investigations. In this work, we focus on the privacy and security of DDF. Our motivations arise from (1) how to track an anonymous- and-malicious data user who leaks only a part of the previously requested data, (2) how to achieve access control while protecting data from untrusted data centers, and (3) how to enable efficient and secure search on the blockchain. To address these issues, we propose Themis: an anonymous and secure DDF scheme with traceable anonymity, private access control, and efficient search. Our framework is boosted by establishing a Trusted Execution Environment in each authority (blockchain node) for securing the uploading, requesting, and searching. To instantiate the framework, we design a secure and robust watermarking scheme in conjunction with decentralized anonymous authentication, a private and fine-grained access control scheme, and an efficient and secure search scheme based on a dynamically updated data structure. We formally define and prove the privacy and security of Themis. We build a prototype with Ethereum and Intel SGX2 to evaluate its performance, which supports processing data from a considerable number of data providers and investigators.@en

Digital forensics is crucial to fight crimes around the world. Decentralized Digital Forensics (DDF) promotes it to another level by channeling the power of blockchain into digital investigations. In this work, we focus on the privacy and security of DDF. Our motivations arise from (1) how to track an anonymous- and-malicious data user who leaks only a part of the previously requested data, (2) how to achieve access control while protecting data from untrusted data centers, and (3) how to enable efficient and secure search on the blockchain. To address these issues, we propose Themis: an anonymous and secure DDF scheme with traceable anonymity, private access control, and efficient search. Our framework is boosted by establishing a Trusted Execution Environment in each authority (blockchain node) for securing the uploading, requesting, and searching. To instantiate the framework, we design a secure and robust watermarking scheme in conjunction with decentralized anonymous authentication, a private and fine-grained access control scheme, and an efficient and secure search scheme based on a dynamically updated data structure. We formally define and prove the privacy and security of Themis. We build a prototype with Ethereum and Intel SGX2 to evaluate its performance, which supports processing data from a considerable number of data providers and investigators.@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