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.
Other than search in the encrypted domain, the concept of search with reduced reference is proposed in privacy-preserving content-based information retrieval to protect the original content and accelerate the search simultaneously @cite_7 @cite_9 @cite_8 . The basic idea therein is to enforce @math -anonymity or @math -diversity properties by raising the ambiguity level of a data collection @cite_45 @cite_1 . Techniques of this paradigm are mostly based on randomized embedding @cite_0 and in particular locality sensitive hashing (LSH) @cite_9 @cite_11 @cite_3 @cite_36 . LSH performs approximate NN search by hashing similar items into the same bucket and those that are distant from one another into different buckets, respectively, with high probabilities. However, LSH by itself does not guarantee privacy @cite_0 @cite_3 @cite_36 . It requires all parties involved in a search to use the same random keys in generating hash codes. Moreover, to achieve a good precision in search, LSH-based algorithms usually require a large number of random hash functions and may increase privacy risks @cite_39 .
@cite_7 @cite_8 @cite_36 @cite_9 @cite_1 @cite_3 @cite_39 @cite_0 @cite_45 @cite_11
2462806717 2533461851 2019586918 2058181105 1975179452 2162511804 1538715284 2541558529
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. We present a novel method to securely determine whether two signals are similar to each other, and apply it to approximate nearest neighbor clustering. The proposed method relies on a locality sensitive hashing scheme based on a secure binary embedding, computed using quantized random projections. Hashes extracted from the signals preserve information about the distance between the signals, provided this distance is small enough. If the distance between the signals is larger than a threshold, then no information about the distance is revealed. Theoretical and experimental justification is provided for this property. Further, when the randomized embedding parameters are unknown, then the mutual information between the hashes of any two signals decays to zero exponentially fast as a function of the l 2 distance between the signals. Taking advantage of this property, we suggest that these binary hashes can be used to perform privacy-preserving nearest neighbor search with significantly lower complexity compared to protocols which use the actual signals. 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. In some domains, the need for data privacy and data sharing conflict. Data obfuscation addresses this dilemma by extending several existing technologies and defining obfuscation properties that quantify the technologies' usefulness and privacy preservation. The Locality Sensitive Hashing (LSH) technique of scalably finding nearest-neighbors can be adapted to enable discovering similar users while preserving their privacy. The key idea is to compute the user profile on the end-user device, apply LSH on the local profile, and use the LSH cluster identifier as the interest group identifier of a user. By properties of LSH, the interest group comprises other users with similar interests. The collective behavior of the members of the interest group is anonymously collected at some aggregation node to generate recommendations for the group members. The quality of recommendation depends on the efficiency of the LSH clustering algorithm, i.e. its capability of gathering similar users. In contrast, with conventional usage of LSH (for scalability and not privacy), in our framework one can not perform a linear search over the cluster members to identify the nearest neighbors and to prune away false positives. A good clustering quality is therefore of functional importance for our system. We report in this work how changing the nature of LSH inputs, which in our case corresponds to the user profile representations, impacts the performance of LSH-based clustering and the final quality of recommendations. We present extensive performance evaluations of the LSH-based privacypreserving recommender system using two large datasets of MovieLens ratings and Delicious bookmarks, respectively. 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. The Handbook of Database Security: Applications & Trends, an edited volume by renowned researchers within data security, provides an up-to-date overview of data security models, techniques, and architectures in a variety of data management applications and settings. This edited volume represents the most comprehensive work on numerous data security aspects published in the last ten years. The Handbook of Database Security: Applications & Trends places a particular focus on data-centric security aspects that reach beyond traditional and well-studied data security aspects in databases. It also covers security in advanced database systems, data privacy and trust management, and data outsourcing, and outlines directions for future research in these fields. The Handbook of Database Security: Applications & Trends is designed for a professional audience composed of practitioners and researchers in industry and academia as a reference book. This volume is also suitable for advanced-level students in computer science interested in the state-of-the-art in data security. In many situations, such as in biometric applications, there is need to encrypt and “hide” data, while simultaneously permitting restricted computations on them. We present a method to securely determine the 2 distance between two signals if they are close enough. This method relies on a locality sensitive hashing scheme based on a secure modular embedding, computed using quantized random projections, being a generalization of previous work in the area. Secure Modular Hashes (SMH) extracted from the signals preserve information about the distance between the signals, hiding other characteristic from the signals. Theoretical properties state that the described scheme provides a mechanism to threshold how much information to reveal, and is also information theoretically secure above this threshold. Finally, experimental results reveal that distances computed from SMH vectors can effectively replace the actual Euclidean distances with minimal degradation.