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

40 Citations (Scopus)


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
Number of pages18
ISBN (Electronic)9783319989891
ISBN (Print)9783319989884
Publication statusPublished - 2018
EventEuropean Symposium On Research In Computer Security 2018 - Barcelona, Spain
Duration: 3 Sept 20187 Sept 2018
Conference number: 23rd (Proceedings)

Publication series

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


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


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

Cite this