Biblio

Nearest neighbor search, a classic way of identifying similar data, can be applied to various areas, including database, machine learning, natural language processing, software engineering, etc. Secure nearest neighbor search aims to find nearest neighbors to a given query point over encrypted data without accessing data in plaintext. It provides privacy protection to datasets when nearest neighbor queries need to be operated by an untrusted party (e.g., a public server). While different solutions have been proposed to support nearest neighbor queries on encrypted data, these existing solutions still encounter critical drawbacks either in efficiency or privacy. In light of the limitations in the current literature, we propose a novel approximate nearest neighbor search solution, referred to as Sparser, by leveraging a combination of space-filling curves, perturbation, and Order-Preserving Encryption. The advantages of Sparser are twofold, strengthening privacy and improving efficiency. Specifically, Sparser pre-processes plaintext data with space-filling curves and perturbation, such that data is sparse, which mitigates leakage abuse attacks and renders stronger privacy. In addition to privacy enhancement, Sparser can efficiently find approximate nearest neighbors over encrypted data with logarithmic time. Through extensive experiments over real-world datasets, we demonstrate that Sparser can achieve strong privacy protection under leakage abuse attacks and minimize search time.

With geographic message dissemination, connected vehicles can be served with traffic information in their proximity, thereby positively impacting road safety, traffic management, or routing. Since such messages are typically relevant in a small geographic area, servers only distribute messages to affected vehicles for efficiency reasons. One main challenge is to maintain scalability of the server infrastructure when collecting location updates from vehicles and determining the relevant group of vehicles when messages are distributed to a geographic relevance area, while at the same time respecting the individual user's privacy in accordance with legal regulations. In this paper, we present a framework for geographic message dissemination following the privacy-by-design and privacy-by-default principles, without having to accept efficiency drawbacks compared to conventional server-client based approaches.