Enabling privacy-assured similarity retrieval over millions of encrypted records

Xingliang Yuan, Helei Cui, Xinyu Wang, Cong Wang

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

21 Citations (Scopus)


Searchable symmetric encryption (SSE) has been studied extensively for its full potential in enabling exact-match queries on encrypted records. Yet, situations for similarity queries remain to be fully explored. In this paper, we design privacy-assured similarity search schemes over millions of encrypted high-dimensional records. Our design employs locality-sensitive hashing (LSH) and SSE, where the LSH hash values of records are treated as keywords fed into the framework of SSE. As direct combination of the two does not facilitate a scalable solution for large datasets, we then leverage a set of advanced hash-based algorithms including multiple-choice hashing, open addressing, and cuckoo hashing, and craft a high performance encrypted index from the ground up. It is not only space efficient, but supports secure and sufficiently accurate similarity search with constant time. Our designs are proved to be secure against adaptive adversaries. The experiment on 10 million encrypted records demonstrates that our designs function in a practical manner.

Original languageEnglish
Title of host publicationComputer Security – ESORICS 2015
Subtitle of host publication20th European Symposium on Research in Computer Security Vienna, Austria, September 21–25, 2015, Proceedings, Part II
EditorsGünther Pernul, Peter Y A Ryan, Edgar Weippl
Place of PublicationCham Switzerland
Number of pages21
ISBN (Electronic)9783319241777
ISBN (Print)9783319241760
Publication statusPublished - 2015
Externally publishedYes
EventEuropean Symposium On Research In Computer Security 2015 - Vienna, Austria
Duration: 23 Sep 201525 Sep 2015
Conference number: 20th
https://link.springer.com/book/10.1007/978-3-319-24174-6 (Proceedings)

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceEuropean Symposium On Research In Computer Security 2015
Abbreviated titleESORICS 2015
Internet address


  • Cloud security
  • Encrypted storage
  • Similarity retrieval

Cite this