Towards an Information Theoretic Analysis of Searchable Encryption (Extended Version)

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

Research output: Book/ReportReportProfessional

34 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 languageUndefined
Place of PublicationEnschede
PublisherCentre for Telematics and Information Technology (CTIT)
Number of pages24
Publication statusPublished - 5 Aug 2008

Publication series

NameCTIT Technical Report Series
PublisherCentre for Telematics and Information Technology, University of Twente
No.DTR08-9/TR-CTIT-08-50
ISSN (Print)1381-3625

Keywords

  • EWI-13176
  • IR-64907
  • METIS-251117
  • SCS-Cybersecurity

Cite this

Sedghi, S., Doumen, J. M., Hartel, P. H., & Jonker, W. (2008). Towards an Information Theoretic Analysis of Searchable Encryption (Extended Version). (CTIT Technical Report Series; No. DTR08-9/TR-CTIT-08-50). Enschede: Centre for Telematics and Information Technology (CTIT).
Sedghi, S. ; Doumen, J.M. ; Hartel, Pieter H. ; Jonker, Willem. / Towards an Information Theoretic Analysis of Searchable Encryption (Extended Version). Enschede : Centre for Telematics and Information Technology (CTIT), 2008. 24 p. (CTIT Technical Report Series; DTR08-9/TR-CTIT-08-50).
@book{71f210fa04454c98a23d53daf81d05be,
title = "Towards an Information Theoretic Analysis of Searchable Encryption (Extended Version)",
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-13176, IR-64907, METIS-251117, SCS-Cybersecurity",
author = "S. Sedghi and J.M. Doumen and Hartel, {Pieter H.} and Willem Jonker",
year = "2008",
month = "8",
day = "5",
language = "Undefined",
series = "CTIT Technical Report Series",
publisher = "Centre for Telematics and Information Technology (CTIT)",
number = "DTR08-9/TR-CTIT-08-50",
address = "Netherlands",

}

Sedghi, S, Doumen, JM, Hartel, PH & Jonker, W 2008, Towards an Information Theoretic Analysis of Searchable Encryption (Extended Version). CTIT Technical Report Series, no. DTR08-9/TR-CTIT-08-50, Centre for Telematics and Information Technology (CTIT), Enschede.

Towards an Information Theoretic Analysis of Searchable Encryption (Extended Version). / Sedghi, S.; Doumen, J.M.; Hartel, Pieter H.; Jonker, Willem.

Enschede : Centre for Telematics and Information Technology (CTIT), 2008. 24 p. (CTIT Technical Report Series; No. DTR08-9/TR-CTIT-08-50).

Research output: Book/ReportReportProfessional

TY - BOOK

T1 - Towards an Information Theoretic Analysis of Searchable Encryption (Extended Version)

AU - Sedghi, S.

AU - Doumen, J.M.

AU - Hartel, Pieter H.

AU - Jonker, Willem

PY - 2008/8/5

Y1 - 2008/8/5

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-13176

KW - IR-64907

KW - METIS-251117

KW - SCS-Cybersecurity

M3 - Report

T3 - CTIT Technical Report Series

BT - Towards an Information Theoretic Analysis of Searchable Encryption (Extended Version)

PB - Centre for Telematics and Information Technology (CTIT)

CY - Enschede

ER -

Sedghi S, Doumen JM, Hartel PH, Jonker W. Towards an Information Theoretic Analysis of Searchable Encryption (Extended Version). Enschede: Centre for Telematics and Information Technology (CTIT), 2008. 24 p. (CTIT Technical Report Series; DTR08-9/TR-CTIT-08-50).