Sub-linear Privacy-preserving Search with Untrusted Server and Semi-honest Parties
|Title||Sub-linear Privacy-preserving Search with Untrusted Server and Semi-honest Parties|
|Publication Type||Journal Article|
|Year of Publication||2016|
|Authors||Riazi, S. M., B. Chen, A. Shrivastava, D. Wallach, and F. Koushanfar|
|Keywords||Garbled Circuits, locality sensitive hashing., Near neighbor search, Privacy-Preserving|
In Near-Neighbor Search (NNS), a new client wants to query a database (held by a server) for the most similar data (near-neighbors) with a certain similarity metric. The Privacy-Preserving variant (PP-NNS) requires that neither server nor the client shall learn anything about the other party’s data except what can be inferred from the outcome of NNS. The overwhelming growth in the size of current datasets and the lack of a truly secure server in the online world render the existing solutions impractical either due to their high computational requirements or non-realistic assumptions which potentially compromise privacy. PP-NNS having query time sub-linear in the size of the database has been proposed as an open research direction in . In this paper, we provide the first such algorithm which has a sub-linear query time and the ability to handle Honest-but-Curious (HbC) parties. At the heart of our proposal lies a secure probabilistic embedding scheme generated from a novel probabilistic transformation over Locality Sensitive Hashing (LSH) family. We provide information theoretic bound for the privacy gauntness and support our theoretical claims using substantial empirical evidence on real-world datasets.