Enabling Privacy-Assured Similarity Retrieval over Millions of Encrypted Records

Xingliang Yuan; Helei Cui; Xinyu Wang; Cong Wang

doi:10.1007/978-3-319-24177-7_3

Enabling Privacy-Assured Similarity Retrieval over Millions of Encrypted Records

Xingliang Yuan
, Helei Cui
, Xinyu Wang
, Cong Wang^*

^*Corresponding author for this work

Department of Computer Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

42 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 language	English
Title of host publication	Computer Security - ESORICS 2015
Subtitle of host publication	20th European Symposium on Research in Computer Security, Vienna, Austria, September 21-25, 2015, Proceedings, Part II
Editors	Günther Pernul, Peter Y A Ryan, Edgar Weippl
Publisher	Springer, Cham
Pages	40-60
ISBN (Electronic)	978-3-319-24177-7
ISBN (Print)	978-3-319-24176-0
DOIs	https://doi.org/10.1007/978-3-319-24177-7_3
Publication status	Published - Sept 2015
Event	20th European Symposium on Research in Computer Security, ESORICS 2015 - Vienna, Austria Duration: 21 Sept 2015 → 25 Sept 2015

Publication series

Name	Lecture Notes in Computer Science (including subseries Security and Cryptology)
Volume	9327
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	20th European Symposium on Research in Computer Security, ESORICS 2015
Place	Austria
City	Vienna
Period	21/09/15 → 25/09/15

Bibliographical note

Full text of this publication does not contain sufficient affiliation information. With consent from the author(s) concerned, the Research Unit(s) information for this record is based on the existing academic department affiliation of the author(s).

Research Keywords

Cloud security
Encrypted storage
Similarity retrieval

Access Output

10.1007/978-3-319-24177-7_3

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Yuan, X., Cui, H., Wang, X., & Wang, C. (2015). Enabling Privacy-Assured Similarity Retrieval over Millions of Encrypted Records. In G. Pernul, P. Y. A. Ryan, & E. Weippl (Eds.), Computer Security - ESORICS 2015: 20th European Symposium on Research in Computer Security, Vienna, Austria, September 21-25, 2015, Proceedings, Part II (pp. 40-60). (Lecture Notes in Computer Science (including subseries Security and Cryptology); Vol. 9327). Springer, Cham. https://doi.org/10.1007/978-3-319-24177-7_3

Yuan, Xingliang ; Cui, Helei ; Wang, Xinyu et al. / Enabling Privacy-Assured Similarity Retrieval over Millions of Encrypted Records. Computer Security - ESORICS 2015: 20th European Symposium on Research in Computer Security, Vienna, Austria, September 21-25, 2015, Proceedings, Part II. editor / Günther Pernul ; Peter Y A Ryan ; Edgar Weippl. Springer, Cham, 2015. pp. 40-60 (Lecture Notes in Computer Science (including subseries Security and Cryptology)).

@inproceedings{69650e03cbf84ab9a41ab80490bda508,

title = "Enabling Privacy-Assured Similarity Retrieval over Millions of Encrypted Records",

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.",

keywords = "Cloud security, Encrypted storage, Similarity retrieval",

author = "Xingliang Yuan and Helei Cui and Xinyu Wang and Cong Wang",

note = "Full text of this publication does not contain sufficient affiliation information. With consent from the author(s) concerned, the Research Unit(s) information for this record is based on the existing academic department affiliation of the author(s).; 20th European Symposium on Research in Computer Security, ESORICS 2015 ; Conference date: 21-09-2015 Through 25-09-2015",

year = "2015",

month = sep,

doi = "10.1007/978-3-319-24177-7\_3",

language = "English",

isbn = "978-3-319-24176-0",

series = "Lecture Notes in Computer Science (including subseries Security and Cryptology)",

publisher = "Springer, Cham",

pages = "40--60",

editor = "Pernul, \{G{\"u}nther \} and Ryan, \{Peter Y A \} and Weippl, \{Edgar \}",

booktitle = "Computer Security - ESORICS 2015",

}

Yuan, X, Cui, H , Wang, X & Wang, C 2015, Enabling Privacy-Assured Similarity Retrieval over Millions of Encrypted Records. in G Pernul, PYA Ryan & E Weippl (eds), Computer Security - ESORICS 2015: 20th European Symposium on Research in Computer Security, Vienna, Austria, September 21-25, 2015, Proceedings, Part II. Lecture Notes in Computer Science (including subseries Security and Cryptology), vol. 9327, Springer, Cham, pp. 40-60, 20th European Symposium on Research in Computer Security, ESORICS 2015, Vienna, Austria, 21/09/15. https://doi.org/10.1007/978-3-319-24177-7_3

Enabling Privacy-Assured Similarity Retrieval over Millions of Encrypted Records. / Yuan, Xingliang; Cui, Helei ; Wang, Xinyu et al.
Computer Security - ESORICS 2015: 20th European Symposium on Research in Computer Security, Vienna, Austria, September 21-25, 2015, Proceedings, Part II. ed. / Günther Pernul; Peter Y A Ryan; Edgar Weippl. Springer, Cham, 2015. p. 40-60 (Lecture Notes in Computer Science (including subseries Security and Cryptology); Vol. 9327).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Enabling Privacy-Assured Similarity Retrieval over Millions of Encrypted Records

AU - Yuan, Xingliang

AU - Cui, Helei

AU - Wang, Xinyu

AU - Wang, Cong

N1 - Full text of this publication does not contain sufficient affiliation information. With consent from the author(s) concerned, the Research Unit(s) information for this record is based on the existing academic department affiliation of the author(s).

PY - 2015/9

Y1 - 2015/9

N2 - 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.

AB - 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.

KW - Cloud security

KW - Encrypted storage

KW - Similarity retrieval

UR - https://www.scopus.com/pages/publications/84951791241

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84951791241&origin=recordpage

U2 - 10.1007/978-3-319-24177-7_3

DO - 10.1007/978-3-319-24177-7_3

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 978-3-319-24176-0

T3 - Lecture Notes in Computer Science (including subseries Security and Cryptology)

SP - 40

EP - 60

BT - Computer Security - ESORICS 2015

A2 - Pernul, Günther

A2 - Ryan, Peter Y A

A2 - Weippl, Edgar

PB - Springer, Cham

T2 - 20th European Symposium on Research in Computer Security, ESORICS 2015

Y2 - 21 September 2015 through 25 September 2015

ER -

Yuan X, Cui H , Wang X , Wang C. Enabling Privacy-Assured Similarity Retrieval over Millions of Encrypted Records. In Pernul G, Ryan PYA, Weippl E, editors, Computer Security - ESORICS 2015: 20th European Symposium on Research in Computer Security, Vienna, Austria, September 21-25, 2015, Proceedings, Part II. Springer, Cham. 2015. p. 40-60. (Lecture Notes in Computer Science (including subseries Security and Cryptology)). doi: 10.1007/978-3-319-24177-7_3

Enabling Privacy-Assured Similarity Retrieval over Millions of Encrypted Records

Abstract

Publication series

Conference

Bibliographical note

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this