Privacy-assured Similarity Search for Large-scale Applications

Year: 2018 Version: v1.0


Big data are usually drawn from varieties of forms: not just texts, but also images, audio, video, and other information-rich content, which are usually represented as high-dimensional data records. In this context, similarity queries are more desired than exact-match queries. Meanwhile, multimedia data often contain sensitive or personal information. Thus, enabling secure content-aware query processing over encrypted multimedia data is very demanding. Yet, most prior solutions on encrypted search are for exact-match queries.

Fig. 1: Privacy-preserving Image Querying Service

To bridge the gap, we first note that this problem could be theoretically handled by a direct combination of locality-sensitive hashing (LSH) and searchable symmetric encryption (SSE), where LSH is a well-studied algorithm for fast similarity search, and SSE is a widely adopted security framework for encrypted search. By treating LSH hash value(s) as keyword(s), one may apply known SSE schemes to realize secure similarity search. However, we observed that such a straightforward solution does not achieve practical scalability and efficiency as the sizes of datasets are continuously growing. Rather than just assembling off-the-shelf designs in a blackbox manner, we consider challenges and requirements in different scenarios, e.g., applications that need to support low latency queries, applications that need to handle streaming data in high rates, and applications deployed in distributed systems. To serve these needs, we develop new constructions from the ground up.


  • Xingliang Yuan, Xinyu Wang, Cong Wang, Anna Squicciarini, and Kui Ren, "Enabling Privacy-preserving Image-centric Social Discovery", In International Conference on Distributed Computing Systems (ICDCS), Madrid, Spain, 1 - 3 July, 2014.
  • Xingliang Yuan, Helei Cui, Xinyu Wang, and Cong Wang, "Enabling Privacy-assured Similarity Retrieval over Millions of Encrypted Records", In European Symposium on Research in Computer Security (ESORICS), Vienna, Austria, 21 - 25 Sep, 2015.
  • Xingliang Yuan, Xinyu Wang, Cong Wang, Jian Weng, and Kui Ren, "Enabling Secure and Fast Indexing for Privacy-assured Healthcare Monitoring via Compressive Sensing", IEEE Transactions on Multimedia, vol. 18, no. 10, pp. 2002-2014, October, 2016.


Xingliang Yuan
Xinyu Wang
Helei Cui
Cong Wang