| Title | Sparser: Secure Nearest Neighbor Search with Space-filling Curves |
| Publication Type | Conference Paper |
| Year of Publication | 2020 |
| Authors | Fang, S., Kennedy, S., Wang, C., Wang, B., Pei, Q., Liu, X. |
| Conference Name | IEEE INFOCOM 2020 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS) |
| Keywords | approximate 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 |
| Abstract | 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. |
| DOI | 10.1109/INFOCOMWKSHPS50562.2020.9162585 |
| Citation Key | fang_sparser_2020 |
Sparser: Secure Nearest Neighbor Search with Space-filling Curves