Towards an Information Theoretic Analysis of Searchable Encryption

S. Sedghi; J.M. Doumen; Pieter H. Hartel; Willem Jonker

doi:10.1007/978-3-540-88625-9_23

Towards an Information Theoretic Analysis of Searchable Encryption

S. Sedghi, J.M. Doumen, Pieter H. Hartel, Willem Jonker

Databases (Former)

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

7 Citations (Scopus)

160 Downloads (Pure)

Abstract

Searchable encryption is a technique that allows a client to store data in encrypted form on a curious server, such that data can be retrieved while leaking a minimal amount of information to the server. Many searchable encryption schemes have been proposed and proved secure in their own computational model. In this paper we propose a generic model for the analysis of searchable encryptions. We then identify the security parameters of searchable encryption schemes and prove information theoretical bounds on the security of the parameters. We argue that perfectly secure searchable encryption schemes cannot be efficient. We classify the seminal schemes in two categories: the schemes that leak information upfront during the storage phase, and schemes that leak some information at every search. This helps designers to choose the right scheme for an application.

Original language	English
Title of host publication	10th international conference on information and communication security
Place of Publication	Berlin
Publisher	Springer
Pages	345-360
Number of pages	24
ISBN (Print)	978-3-540-88624-2
DOIs	https://doi.org/10.1007/978-3-540-88625-9_23
Publication status	Published - 22 Oct 2008
Event	10th International Conference on Information and Communications Security, ICICS 2008 - Hyatt Regency, Birmingham, United Kingdom Duration: 20 Oct 2008 → 22 Oct 2008 Conference number: 10 http://events.cs.bham.ac.uk/icics08/

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Number	1
Volume	5308
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	10th International Conference on Information and Communications Security, ICICS 2008
Abbreviated title	ICICS
Country/Territory	United Kingdom
City	Birmingham
Period	20/10/08 → 22/10/08
Internet address	http://events.cs.bham.ac.uk/icics08/

Keywords

EWI-13866
IR-62495
METIS-252082
SCS-Cybersecurity

Access to Document

10.1007/978-3-540-88625-9_23

Sedghi2008towardsAccepted author version, 232 KB

Cite this

@inproceedings{6ea5d3fe664e48e7a73e245351c85769,

title = "Towards an Information Theoretic Analysis of Searchable Encryption",

abstract = "Searchable encryption is a technique that allows a client to store data in encrypted form on a curious server, such that data can be retrieved while leaking a minimal amount of information to the server. Many searchable encryption schemes have been proposed and proved secure in their own computational model. In this paper we propose a generic model for the analysis of searchable encryptions. We then identify the security parameters of searchable encryption schemes and prove information theoretical bounds on the security of the parameters. We argue that perfectly secure searchable encryption schemes cannot be efficient. We classify the seminal schemes in two categories: the schemes that leak information upfront during the storage phase, and schemes that leak some information at every search. This helps designers to choose the right scheme for an application.",

keywords = "EWI-13866, IR-62495, METIS-252082, SCS-Cybersecurity",

author = "S. Sedghi and J.M. Doumen and Hartel, {Pieter H.} and Willem Jonker",

year = "2008",

month = oct,

day = "22",

doi = "10.1007/978-3-540-88625-9_23",

language = "English",

isbn = "978-3-540-88624-2",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

number = "1",

pages = "345--360",

booktitle = "10th international conference on information and communication security",

address = "Germany",

note = "10th International Conference on Information and Communications Security, ICICS 2008, ICICS ; Conference date: 20-10-2008 Through 22-10-2008",

url = "http://events.cs.bham.ac.uk/icics08/",

}

Sedghi, S, Doumen, JM, Hartel, PH & Jonker, W 2008, Towards an Information Theoretic Analysis of Searchable Encryption. in 10th international conference on information and communication security. Lecture Notes in Computer Science, no. 1, vol. 5308, Springer, Berlin, pp. 345-360, 10th International Conference on Information and Communications Security, ICICS 2008, Birmingham, United Kingdom, 20/10/08. https://doi.org/10.1007/978-3-540-88625-9_23

Towards an Information Theoretic Analysis of Searchable Encryption. / Sedghi, S.; Doumen, J.M.; Hartel, Pieter H. et al.
10th international conference on information and communication security. Berlin: Springer, 2008. p. 345-360 (Lecture Notes in Computer Science; Vol. 5308, No. 1).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Towards an Information Theoretic Analysis of Searchable Encryption

AU - Sedghi, S.

AU - Doumen, J.M.

AU - Hartel, Pieter H.

AU - Jonker, Willem

N1 - Conference code: 10

PY - 2008/10/22

Y1 - 2008/10/22

N2 - Searchable encryption is a technique that allows a client to store data in encrypted form on a curious server, such that data can be retrieved while leaking a minimal amount of information to the server. Many searchable encryption schemes have been proposed and proved secure in their own computational model. In this paper we propose a generic model for the analysis of searchable encryptions. We then identify the security parameters of searchable encryption schemes and prove information theoretical bounds on the security of the parameters. We argue that perfectly secure searchable encryption schemes cannot be efficient. We classify the seminal schemes in two categories: the schemes that leak information upfront during the storage phase, and schemes that leak some information at every search. This helps designers to choose the right scheme for an application.

AB - Searchable encryption is a technique that allows a client to store data in encrypted form on a curious server, such that data can be retrieved while leaking a minimal amount of information to the server. Many searchable encryption schemes have been proposed and proved secure in their own computational model. In this paper we propose a generic model for the analysis of searchable encryptions. We then identify the security parameters of searchable encryption schemes and prove information theoretical bounds on the security of the parameters. We argue that perfectly secure searchable encryption schemes cannot be efficient. We classify the seminal schemes in two categories: the schemes that leak information upfront during the storage phase, and schemes that leak some information at every search. This helps designers to choose the right scheme for an application.

KW - EWI-13866

KW - IR-62495

KW - METIS-252082

KW - SCS-Cybersecurity

U2 - 10.1007/978-3-540-88625-9_23

DO - 10.1007/978-3-540-88625-9_23

M3 - Conference contribution

SN - 978-3-540-88624-2

T3 - Lecture Notes in Computer Science

SP - 345

EP - 360

BT - 10th international conference on information and communication security

PB - Springer

CY - Berlin

T2 - 10th International Conference on Information and Communications Security, ICICS 2008

Y2 - 20 October 2008 through 22 October 2008

ER -

Towards an Information Theoretic Analysis of Searchable Encryption

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this