A Survey of Provably Secure Searchable Encryption

Research output: Contribution to journalArticleAcademicpeer-review

  • 89 Citations

Abstract

We survey the notion of provably secure Searchable Encryption (SE) by giving a complete and comprehensive overview of the two main SE techniques: Searchable Symmetric Encryption (SSE) and Public Key Encryption with Keyword Search (PEKS). Since the pioneering work of Song, Wagner and Perrig (IEEE S&P ’00), the field of provably secure SE has expanded to the point where we felt that taking stock would provide benefit to the community. The survey has been written primarily for the non-specialist who has a basic information security background. Thus, we sacrifice full details and proofs of individual constructions in favor of an overview of the underlying key techniques. We categorize and compare the different SE schemes in terms of their security, efficiency, and functionality. For the experienced researcher we point out connections between the many approaches to SE and identify open research problems. Two major conclusions can be drawn from our work. While the so-called IND-CKA2 security notion becomes prevalent in the literature and efficient (sub-linear) SE schemes meeting this notion exist in the symmetric setting, achieving this strong form of security efficiently in the asymmetric setting remains an open problem. We observe that in multi-recipient SE schemes, regardless of their efficiency drawbacks, there is a noticeable lack of query expressiveness which hinders deployment in practice.
LanguageUndefined
Article number18
Pages18:1-18:51
Number of pages47
JournalACM computing surveys
Volume47
Issue number2
DOIs
Publication statusPublished - Aug 2014

Keywords

  • SCS-Cybersecurity
  • CR-H.3.0
  • CR-A.1
  • METIS-304114
  • EWI-24788
  • IR-91214
  • CR-E.3

Cite this

@article{65db4912deb243f38fee540b1f632e50,
title = "A Survey of Provably Secure Searchable Encryption",
abstract = "We survey the notion of provably secure Searchable Encryption (SE) by giving a complete and comprehensive overview of the two main SE techniques: Searchable Symmetric Encryption (SSE) and Public Key Encryption with Keyword Search (PEKS). Since the pioneering work of Song, Wagner and Perrig (IEEE S&P ’00), the field of provably secure SE has expanded to the point where we felt that taking stock would provide benefit to the community. The survey has been written primarily for the non-specialist who has a basic information security background. Thus, we sacrifice full details and proofs of individual constructions in favor of an overview of the underlying key techniques. We categorize and compare the different SE schemes in terms of their security, efficiency, and functionality. For the experienced researcher we point out connections between the many approaches to SE and identify open research problems. Two major conclusions can be drawn from our work. While the so-called IND-CKA2 security notion becomes prevalent in the literature and efficient (sub-linear) SE schemes meeting this notion exist in the symmetric setting, achieving this strong form of security efficiently in the asymmetric setting remains an open problem. We observe that in multi-recipient SE schemes, regardless of their efficiency drawbacks, there is a noticeable lack of query expressiveness which hinders deployment in practice.",
keywords = "SCS-Cybersecurity, CR-H.3.0, CR-A.1, METIS-304114, EWI-24788, IR-91214, CR-E.3",
author = "C.T. B{\"o}sch and Hartel, {Pieter H.} and Willem Jonker and Andreas Peter",
note = "eemcs-eprint-24788",
year = "2014",
month = "8",
doi = "10.1145/2636328",
language = "Undefined",
volume = "47",
pages = "18:1--18:51",
journal = "ACM computing surveys",
issn = "0360-0300",
publisher = "Association for Computing Machinery",
number = "2",

}

A Survey of Provably Secure Searchable Encryption. / Bösch, C.T.; Hartel, Pieter H.; Jonker, Willem; Peter, Andreas.

In: ACM computing surveys, Vol. 47, No. 2, 18, 08.2014, p. 18:1-18:51.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - A Survey of Provably Secure Searchable Encryption

AU - Bösch, C.T.

AU - Hartel, Pieter H.

AU - Jonker, Willem

AU - Peter, Andreas

N1 - eemcs-eprint-24788

PY - 2014/8

Y1 - 2014/8

N2 - We survey the notion of provably secure Searchable Encryption (SE) by giving a complete and comprehensive overview of the two main SE techniques: Searchable Symmetric Encryption (SSE) and Public Key Encryption with Keyword Search (PEKS). Since the pioneering work of Song, Wagner and Perrig (IEEE S&P ’00), the field of provably secure SE has expanded to the point where we felt that taking stock would provide benefit to the community. The survey has been written primarily for the non-specialist who has a basic information security background. Thus, we sacrifice full details and proofs of individual constructions in favor of an overview of the underlying key techniques. We categorize and compare the different SE schemes in terms of their security, efficiency, and functionality. For the experienced researcher we point out connections between the many approaches to SE and identify open research problems. Two major conclusions can be drawn from our work. While the so-called IND-CKA2 security notion becomes prevalent in the literature and efficient (sub-linear) SE schemes meeting this notion exist in the symmetric setting, achieving this strong form of security efficiently in the asymmetric setting remains an open problem. We observe that in multi-recipient SE schemes, regardless of their efficiency drawbacks, there is a noticeable lack of query expressiveness which hinders deployment in practice.

AB - We survey the notion of provably secure Searchable Encryption (SE) by giving a complete and comprehensive overview of the two main SE techniques: Searchable Symmetric Encryption (SSE) and Public Key Encryption with Keyword Search (PEKS). Since the pioneering work of Song, Wagner and Perrig (IEEE S&P ’00), the field of provably secure SE has expanded to the point where we felt that taking stock would provide benefit to the community. The survey has been written primarily for the non-specialist who has a basic information security background. Thus, we sacrifice full details and proofs of individual constructions in favor of an overview of the underlying key techniques. We categorize and compare the different SE schemes in terms of their security, efficiency, and functionality. For the experienced researcher we point out connections between the many approaches to SE and identify open research problems. Two major conclusions can be drawn from our work. While the so-called IND-CKA2 security notion becomes prevalent in the literature and efficient (sub-linear) SE schemes meeting this notion exist in the symmetric setting, achieving this strong form of security efficiently in the asymmetric setting remains an open problem. We observe that in multi-recipient SE schemes, regardless of their efficiency drawbacks, there is a noticeable lack of query expressiveness which hinders deployment in practice.

KW - SCS-Cybersecurity

KW - CR-H.3.0

KW - CR-A.1

KW - METIS-304114

KW - EWI-24788

KW - IR-91214

KW - CR-E.3

U2 - 10.1145/2636328

DO - 10.1145/2636328

M3 - Article

VL - 47

SP - 18:1-18:51

JO - ACM computing surveys

T2 - ACM computing surveys

JF - ACM computing surveys

SN - 0360-0300

IS - 2

M1 - 18

ER -