Towards efficient verifiable conjunctive keyword search for large encrypted database

Jianfeng Wang, Xiaofeng Chen, Shi-Feng Sun, Joseph K. Liu, Man Ho Au, Zhi-Hui Zhan

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

Abstract

Searchable Symmetric Encryption (SSE) enables a client to securely outsource large encrypted database to a server while supporting efficient keyword search. Most of the existing works are designed against the honest-but-curious server. That is, the server will be curious but execute the protocol in an honest manner. Recently, some researchers presented various verifiable SSE schemes that can resist to the malicious server, where the server may not honestly perform all the query operations. However, they either only considered single-keyword search or cannot handle very large database. To address this challenge, we propose a new verifiable conjunctive keyword search scheme by leveraging accumulator. Our proposed scheme can not only ensure verifiability of search result even if an empty set is returned but also support efficient conjunctive keyword search with sublinear overhead. Besides, the verification cost of our construction is independent of the size of search result. In addition, we introduce a sample check method for verifying the completeness of search result with a high probability, which can significantly reduce the computation cost on the client side. Security and efficiency evaluation demonstrate that the proposed scheme not only can achieve high security goals but also has a comparable performance.

Original languageEnglish
Title of host publicationComputer Security
Subtitle of host publication23rd European Symposium on Research in Computer Security, ESORICS 2018 Barcelona, Spain, September 3–7, 2018 Proceedings, Part II
EditorsJavier Lopez, Jianying Zhou, Miguel Soriano
Place of PublicationCham Switzerland
PublisherSpringer
Pages83-100
Number of pages18
ISBN (Electronic)9783319989891
ISBN (Print)9783319989884
DOIs
Publication statusPublished - 2018
EventEuropean Symposium On Research In Computer Security 2018 - Barcelona, Spain
Duration: 3 Sep 20187 Sep 2018
Conference number: 23rd
https://esorics2018.upc.edu/

Publication series

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

Conference

ConferenceEuropean Symposium On Research In Computer Security 2018
Abbreviated titleESORICS 2018
CountrySpain
CityBarcelona
Period3/09/187/09/18
Internet address

Keywords

  • Accumulator
  • Conjunctive keyword search
  • Searchable encryption
  • Verifiable search

Cite this

Wang, J., Chen, X., Sun, S-F., Liu, J. K., Au, M. H., & Zhan, Z-H. (2018). Towards efficient verifiable conjunctive keyword search for large encrypted database. In J. Lopez, J. Zhou, & M. Soriano (Eds.), Computer Security: 23rd European Symposium on Research in Computer Security, ESORICS 2018 Barcelona, Spain, September 3–7, 2018 Proceedings, Part II (pp. 83-100). (Lecture Notes in Computer Science ; Vol. 11099 ). Cham Switzerland: Springer. https://doi.org/10.1007/978-3-319-98989-1_5
Wang, Jianfeng ; Chen, Xiaofeng ; Sun, Shi-Feng ; Liu, Joseph K. ; Au, Man Ho ; Zhan, Zhi-Hui. / Towards efficient verifiable conjunctive keyword search for large encrypted database. Computer Security: 23rd European Symposium on Research in Computer Security, ESORICS 2018 Barcelona, Spain, September 3–7, 2018 Proceedings, Part II. editor / Javier Lopez ; Jianying Zhou ; Miguel Soriano. Cham Switzerland : Springer, 2018. pp. 83-100 (Lecture Notes in Computer Science ).
@inproceedings{236d6ec97e4745619baf698d2beee362,
title = "Towards efficient verifiable conjunctive keyword search for large encrypted database",
abstract = "Searchable Symmetric Encryption (SSE) enables a client to securely outsource large encrypted database to a server while supporting efficient keyword search. Most of the existing works are designed against the honest-but-curious server. That is, the server will be curious but execute the protocol in an honest manner. Recently, some researchers presented various verifiable SSE schemes that can resist to the malicious server, where the server may not honestly perform all the query operations. However, they either only considered single-keyword search or cannot handle very large database. To address this challenge, we propose a new verifiable conjunctive keyword search scheme by leveraging accumulator. Our proposed scheme can not only ensure verifiability of search result even if an empty set is returned but also support efficient conjunctive keyword search with sublinear overhead. Besides, the verification cost of our construction is independent of the size of search result. In addition, we introduce a sample check method for verifying the completeness of search result with a high probability, which can significantly reduce the computation cost on the client side. Security and efficiency evaluation demonstrate that the proposed scheme not only can achieve high security goals but also has a comparable performance.",
keywords = "Accumulator, Conjunctive keyword search, Searchable encryption, Verifiable search",
author = "Jianfeng Wang and Xiaofeng Chen and Shi-Feng Sun and Liu, {Joseph K.} and Au, {Man Ho} and Zhi-Hui Zhan",
year = "2018",
doi = "10.1007/978-3-319-98989-1_5",
language = "English",
isbn = "9783319989884",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "83--100",
editor = "Javier Lopez and Jianying Zhou and Miguel Soriano",
booktitle = "Computer Security",

}

Wang, J, Chen, X, Sun, S-F, Liu, JK, Au, MH & Zhan, Z-H 2018, Towards efficient verifiable conjunctive keyword search for large encrypted database. in J Lopez, J Zhou & M Soriano (eds), Computer Security: 23rd European Symposium on Research in Computer Security, ESORICS 2018 Barcelona, Spain, September 3–7, 2018 Proceedings, Part II. Lecture Notes in Computer Science , vol. 11099 , Springer, Cham Switzerland, pp. 83-100, European Symposium On Research In Computer Security 2018, Barcelona, Spain, 3/09/18. https://doi.org/10.1007/978-3-319-98989-1_5

Towards efficient verifiable conjunctive keyword search for large encrypted database. / Wang, Jianfeng; Chen, Xiaofeng; Sun, Shi-Feng; Liu, Joseph K.; Au, Man Ho; Zhan, Zhi-Hui.

Computer Security: 23rd European Symposium on Research in Computer Security, ESORICS 2018 Barcelona, Spain, September 3–7, 2018 Proceedings, Part II. ed. / Javier Lopez; Jianying Zhou; Miguel Soriano. Cham Switzerland : Springer, 2018. p. 83-100 (Lecture Notes in Computer Science ; Vol. 11099 ).

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

TY - GEN

T1 - Towards efficient verifiable conjunctive keyword search for large encrypted database

AU - Wang, Jianfeng

AU - Chen, Xiaofeng

AU - Sun, Shi-Feng

AU - Liu, Joseph K.

AU - Au, Man Ho

AU - Zhan, Zhi-Hui

PY - 2018

Y1 - 2018

N2 - Searchable Symmetric Encryption (SSE) enables a client to securely outsource large encrypted database to a server while supporting efficient keyword search. Most of the existing works are designed against the honest-but-curious server. That is, the server will be curious but execute the protocol in an honest manner. Recently, some researchers presented various verifiable SSE schemes that can resist to the malicious server, where the server may not honestly perform all the query operations. However, they either only considered single-keyword search or cannot handle very large database. To address this challenge, we propose a new verifiable conjunctive keyword search scheme by leveraging accumulator. Our proposed scheme can not only ensure verifiability of search result even if an empty set is returned but also support efficient conjunctive keyword search with sublinear overhead. Besides, the verification cost of our construction is independent of the size of search result. In addition, we introduce a sample check method for verifying the completeness of search result with a high probability, which can significantly reduce the computation cost on the client side. Security and efficiency evaluation demonstrate that the proposed scheme not only can achieve high security goals but also has a comparable performance.

AB - Searchable Symmetric Encryption (SSE) enables a client to securely outsource large encrypted database to a server while supporting efficient keyword search. Most of the existing works are designed against the honest-but-curious server. That is, the server will be curious but execute the protocol in an honest manner. Recently, some researchers presented various verifiable SSE schemes that can resist to the malicious server, where the server may not honestly perform all the query operations. However, they either only considered single-keyword search or cannot handle very large database. To address this challenge, we propose a new verifiable conjunctive keyword search scheme by leveraging accumulator. Our proposed scheme can not only ensure verifiability of search result even if an empty set is returned but also support efficient conjunctive keyword search with sublinear overhead. Besides, the verification cost of our construction is independent of the size of search result. In addition, we introduce a sample check method for verifying the completeness of search result with a high probability, which can significantly reduce the computation cost on the client side. Security and efficiency evaluation demonstrate that the proposed scheme not only can achieve high security goals but also has a comparable performance.

KW - Accumulator

KW - Conjunctive keyword search

KW - Searchable encryption

KW - Verifiable search

UR - http://www.scopus.com/inward/record.url?scp=85051868130&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-98989-1_5

DO - 10.1007/978-3-319-98989-1_5

M3 - Conference Paper

SN - 9783319989884

T3 - Lecture Notes in Computer Science

SP - 83

EP - 100

BT - Computer Security

A2 - Lopez, Javier

A2 - Zhou, Jianying

A2 - Soriano, Miguel

PB - Springer

CY - Cham Switzerland

ER -

Wang J, Chen X, Sun S-F, Liu JK, Au MH, Zhan Z-H. Towards efficient verifiable conjunctive keyword search for large encrypted database. In Lopez J, Zhou J, Soriano M, editors, Computer Security: 23rd European Symposium on Research in Computer Security, ESORICS 2018 Barcelona, Spain, September 3–7, 2018 Proceedings, Part II. Cham Switzerland: Springer. 2018. p. 83-100. (Lecture Notes in Computer Science ). https://doi.org/10.1007/978-3-319-98989-1_5