Paper 2019/1222

Sub-Linear Privacy-Preserving Near-Neighbor Search

M. Sadegh Riazi, Beidi Chen, Anshumali Shrivastava, Dan Wallach, and Farinaz Koushanfar

Abstract

In Near-Neighbor Search (NNS), a client queries a database (held by a server) for the most similar data (near-neighbors) given a certain similarity metric. The Privacy-Preserving variant (PP-NNS) requires that neither server nor the client shall learn information 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 suggested as an open research direction by Li et al. (CCSW’15). In this paper, we provide the first such algorithm, called Privacy-Preserving Locality Sensitive Indexing (SLSI) which has a sub-linear query time and the ability to handle honest-but-curious parties. At the heart of our proposal lies a secure binary embedding scheme generated from a novel probabilistic transformation over locality sensitive hashing family. We provide information-theoretic bound for the privacy guarantees and support our theoretical claims using substantial empirical evidence on real-world datasets.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Near-neighbor searchprivacylocality sensitive hashingsimilarity search
Contact author(s)
sadeghriazi @ gmail com
History
2019-10-21: received
Short URL
https://ia.cr/2019/1222
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1222,
      author = {M.  Sadegh Riazi and Beidi Chen and Anshumali Shrivastava and Dan Wallach and Farinaz Koushanfar},
      title = {Sub-Linear Privacy-Preserving Near-Neighbor Search},
      howpublished = {Cryptology {ePrint} Archive, Paper 2019/1222},
      year = {2019},
      url = {https://eprint.iacr.org/2019/1222}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.