  Similarity search is essential to many important applications and often
involves searching at scale on high-dimensional data based on their similarity
to a query. In biometric applications, recent vulnerability studies have shown
that adversarial machine learning can compromise biometric recognition systems
by exploiting the biometric similarity information. Existing methods for
biometric privacy protection are in general based on pairwise matching of
secured biometric templates and have inherent limitations in search efficiency
and scalability. In this paper, we propose an inference-based framework for
privacy-preserving similarity search in Hamming space. Our approach builds on
an obfuscated distance measure that can conceal Hamming distance in a dynamic
interval. Such a mechanism enables us to systematically design statistically
reliable methods for retrieving most likely candidates without knowing the
exact distance values. We further propose to apply Montgomery multiplication
for generating search indexes that can withstand adversarial similarity
analysis, and show that information leakage in randomized Montgomery domains
can be made negligibly small. Our experiments on public biometric datasets
demonstrate that the inference-based approach can achieve a search accuracy
close to the best performance possible with secure computation methods, but the
associated cost is reduced by orders of magnitude compared to cryptographic
primitives.
