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.
Privacy-enhanced variants of LSH are recently proposed by combining LSH with cryptographic or information-theoretic protocols @cite_0 . The privacy protection framework proposed in @cite_9 generates a partial query instance by omitting certain bits in one or more sub-hash values to increase the ambiguity of query information for the server. The hash values of retrieved candidates are returned to the client for refinement. The framework is extended in @cite_8 where partial encryption is performed on the hash code of each item to prevent an untrustworthy server from precisely linking queries and database records. In particular, the server uses the unencrypted part of each item for approximate indexing and search while the client uses the encrypted part for re-ranking the candidates received from the server. To limit the number of candidates sent to the client, the server performs a preliminary ranking based on the computed from the unencrypted part. The trade-off between privacy and utility of a search at the server side is therefore controlled by the number of unencrypted bits. We call this approach LSH + partial distance'' for brevity and will use it as one baseline approach for performance comparison.
@cite_0 @cite_9 @cite_8
2162511804 2019586918 2462806717
Comparing two signals is one of the most essential and prevalent tasks in signal processing. A large number of applications fundamentally rely on determining the answers to the following two questions: 1) How should two signals be compared? 2) Given a set of signals and a query signal, which signals are the nearest neighbors (NNs) of the query signal, i.e., which signals in the database are most similar to the query signal? The NN search problem is defined as follows: Given a set S containing points in a metric space M, and a query point x !M, find the point in S that is closest to x. The problem can be extended to K-NN, i.e., determining the K signals nearest to x. In this context, the points in question are signals, such as images, videos, or other waveforms. The qualifier closest refers to a distance metric, such as the Euclidean distance or Manhattan distance between pairs of points in S. Finding the NN of the query point should be at most linear in the database size and is a well-studied problem in conventional NN settings. We propose a privacy protection framework for large-scale content-based information retrieval. It offers two layers of protection. First, robust hash values are used as queries to prevent revealing original content or features. Second, the client can choose to omit certain bits in a hash value to further increase the ambiguity for the server. Due to the reduced information, it is computationally difficult for the server to know the client’s interest. The server has to return the hash values of all possible candidates to the client. The client performs a search within the candidate list to find the best match. Since only hash values are exchanged between the client and the server, the privacy of both parties is protected. We introduce the concept oftunable privacy, where the privacy protection level can be adjusted according to a policy. It is realized through hash-based piecewise inverted indexing. The idea is to divide a feature vector into pieces and index each piece with a subhash value. Each subhash value is associated with an inverted index list. The framework has been extensively tested using a large image database. We have evaluated both retrieval performance and privacy-preserving performance for a particular content identification application. Two different constructions of robust hash algorithms are used. One is based on random projections; the other is based on the discrete wavelet transform. Both algorithms exhibit satisfactory performance in comparison with state-of-the-art retrieval schemes. The results show that the privacy enhancement slightly improves the retrieval performance. We consider the majority voting attack for estimating the query category and identification. Experiment results show that this attack is a threat when there are near-duplicates, but the success rate decreases with the number of omitted bits and the number of distinct items. This work proposes a privacy-protection framework for an important application called outsourced media search . This scenario involves a data owner, a client, and an untrusted server, where the owner outsources a search service to the server. Due to lack of trust, the privacy of the client and the owner should be protected. The framework relies on multimedia hashing and symmetric encryption. It requires involved parties to participate in a privacy-enhancing protocol. Additional processing steps are carried out by the owner and the client: (i) before outsourcing low-level media features to the server, the owner has to one-way hash them, and partially encrypt each hash-value; (ii) the client completes the similarity search by re-ranking the most similar candidates received from the server. One-way hashing and encryption add ambiguity to data and make it difficult for the server to infer contents from database items and queries, so the privacy of both the owner and the client is enforced. The proposed framework realizes trade-offs among strength of privacy enforcement, quality of search, and complexity, because the information loss can be tuned during hashing and encryption. Extensive experiments demonstrate the effectiveness and the flexibility of the framework.