Privacy-Preserving Similarity Joins Over Encrypted Data
- 28 June 2017
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Forensics and Security
- Vol. 12 (11) , 2763-2775
Abstract
Similarity search on high-dimensional data has been intensively studied for data processing and analytics. Despite its broad applicability, data security and privacy concerns along the trend of data outsourcing have not been fully addressed. In this paper, we investigate privacy-preserving similarity join queries, i.e., a pivotal primitive of similarity search that finds pairwise similar data points across two data sets. We start from locality-sensitive hashing and searchable symmetric encryption, i.e., the most practical techniques for similarity search and encrypted search, respectively. However, the immediate combination of two techniques discloses the distribution of the query set, which is exploitable to compromise the confidentiality of queries. To enhance the security, we propose the frequency hiding query scheme, which allows the server to see the flattened query distribution only. To improve the scalability, we further design the result sharing query scheme, which processes a small portion of query points and shares the results with other nearby points. Besides, we set up a strict constraint to carefully select query points to achieve “as-strong-as-possible” guarantees. We formalize the leakage functions in the context of similarity joins, and conduct rigorous security analysis. We implement and evaluate the proposed query schemes on Azure cloud. Experimental results indicate that they have different tradeoffs on security, efficiency, and accuracy, which can flexibly be used for different deployment scenarios.Keywords
Funding Information
- Research Grants Council of HK (CityU 11276816, CityU C1008-16G)
- CityU of HK (CityU 9680157, CityU 9678126)
- Natural Science Foundation of China (61572412)
- Innovation and Technology Commission of HK under ITF Project (ITS/307/15)
- Microsoft Azure Grant for Research
This publication has 23 references indexed in Scilit:
- Searchable Encryption over Feature-Rich DataIEEE Transactions on Dependable and Secure Computing, 2016
- I/O-Efficient Similarity Join2015
- Leakage-Abuse Attacks Against Searchable Encryption2015
- GRECS2015
- Harnessing encrypted data in cloud for secure and efficient image sharing from mobile devices2015
- Searchable Encryption with Secure and Efficient Updates2014
- Secure k-nearest neighbor query over encrypted data in outsourced environments2014
- Locality-sensitive hashing scheme based on dynamic collision counting2012
- Order-Preserving Encryption Revisited: Improved Security Analysis and Alternative Solutions2011
- Searchable symmetric encryption2006