Visible to the public Sparser: Secure Nearest Neighbor Search with Space-filling Curves

TitleSparser: Secure Nearest Neighbor Search with Space-filling Curves
Publication TypeConference Paper
Year of Publication2020
AuthorsFang, S., Kennedy, S., Wang, C., Wang, B., Pei, Q., Liu, X.
Conference NameIEEE INFOCOM 2020 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)
Keywordsapproximate nearest neighbor search solution, approximate nearest neighbors, approximation theory, cryptography, Curve fitting, data privacy, encrypted data, logarithmic time, Measurement, nearest neighbor queries, nearest neighbor search, nearest neighbour methods, order-preserving encryption, perturbation, Predictive Metrics, pubcrawl, query processing, secure nearest neighbor search, Space-filling curve, space-filling curves, space-filling perturbation, Sparser pre-processes plaintext data, strengthening privacy
AbstractNearest 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.
Citation Keyfang_sparser_2020