  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 introduces the
notion of inherent shared secrecy based on the support intersection of sparse
codes. This approach is `fairness-aware', in the sense that any point in the
neighborhood has an equiprobable chance to be chosen. Our approach can be
applied to raw data, latent representation of autoencoders, and aggregated
local descriptors. The proposed method is tested on both synthetic i.i.d data
and real large-scale image databases.
