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)

Abstract

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
PublisherSpringer
Pages40-60
Number of pages21
ISBN (Electronic)9783319241777
ISBN (Print)9783319241760
DOIs
Publication statusPublished - 2015
Externally publishedYes
EventEuropean Symposium On Research In Computer Security 2015 - Vienna, Austria
Duration: 23 Sep 201525 Sep 2015
Conference number: 20th
http://esorics2015.sba-research.org/
https://link.springer.com/book/10.1007/978-3-319-24174-6 (Proceedings)

Publication series

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

Conference

ConferenceEuropean Symposium On Research In Computer Security 2015
Abbreviated titleESORICS 2015
CountryAustria
CityVienna
Period23/09/1525/09/15
Internet address

Keywords

  • Cloud security
  • Encrypted storage
  • Similarity retrieval

Cite this