Sub-Linear Privacy-Preserving Near-Neighbor Search
In Near-Neighbor Search (NNS), a new 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 {\it 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 Secure 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.
Code (0)
등록된 구현이 없습니다.
Tasks
Privacy PreservingSimilar Papers 제목 키워드 기반
Privacy Preserving Identification Using Sparse Approximation with Ambiguization
In this paper, we consider a privacy preserving encoding framework for identification applications covering biometrics, physical object security and the Internet of Things (IoT). The proposed framework is based on a spar…
Privacy PreservingPrivacy-Preserving Near Neighbor Search via Sparse Coding with Ambiguation
In this paper, we propose a framework for privacy-preserving approximate near neighbor search via stochastic sparsifying encoding. The core of the framework relies on sparse coding with ambiguation (SCA) mechanism that i…
FairnessPrivacy PreservingPrivacy-Preserving Adaptive Traffic Signal Control in a Connected Vehicle Environment
Although Connected Vehicles (CVs) have demonstrated tremendous potential to enhance traffic operations, they can impose privacy risks on individual travelers, e.g., leaking sensitive information about their frequently vi…
Privacy PreservingTraffic Signal ControlCommunication-efficient and Differentially-private Distributed Nash Equilibrium Seeking with Linear Convergence
The distributed computation of a Nash equilibrium (NE) for non-cooperative games is gaining increased attention recently. Due to the nature of distributed systems, privacy and communication efficiency are two critical co…
Privacy PreservingCooperative Control of Multi-Channel Linear Systems with Self-Organizing Private Agents
Cooperative behavior design for multi-agent systems with collective tasks is a critical issue in promoting swarm intelligence. This paper investigates cooperative control for a multi-channel system, where each channel is…
Privacy Preserving