Adaptively Secure Computationally Efficient Searchable Symmetric Encryption

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

Research output: Book/ReportReportProfessional

24 Downloads (Pure)

Abstract

Searchable encryption is a technique that allows a client to store documents on a server in encrypted form. Stored documents can be retrieved selectively while revealing as little information as possible to the server. In the symmetric searchable encryption domain, the storage and the retrieval are performed by the same client. Most conventional searchable encryption schemes suffer from two disadvantages. First, searching the stored documents takes time linear in the size of the database, and/or uses heavy arithmetic operations. Secondly, the existing schemes do not consider adaptive attackers; a search-query will reveal information even about documents stored in the future. If they do consider this, it is at a significant cost to updates. In this paper we propose a novel symmetric searchable encryption scheme that offers searching at constant time in the number of unique keywords stored on the server. We present two variants of the basic scheme which differ in the efficiency of search and update. We show how each scheme could be used in a personal health record system.
Original languageUndefined
Place of PublicationEnschede
PublisherDistributed and Embedded Security (DIES)
Number of pages17
Publication statusPublished - 27 Apr 2009

Publication series

NameCTIT Technical Report Series
PublisherCentre for Telematics and Information Technology, University of Twente
No.TR-CTIT-09-13
ISSN (Print)1381-3625

Keywords

  • Searchable Encryption
  • METIS-263829
  • IR-65475
  • EWI-15312
  • SCS-Cybersecurity
  • Efficient Update
  • Efficient Search

Cite this

Sedghi, S., van Liesdonk, P., Doumen, J. M., Hartel, P. H., & Jonker, W. (2009). Adaptively Secure Computationally Efficient Searchable Symmetric Encryption. (CTIT Technical Report Series; No. TR-CTIT-09-13). Enschede: Distributed and Embedded Security (DIES).
Sedghi, S. ; van Liesdonk, P. ; Doumen, J.M. ; Hartel, Pieter H. ; Jonker, Willem. / Adaptively Secure Computationally Efficient Searchable Symmetric Encryption. Enschede : Distributed and Embedded Security (DIES), 2009. 17 p. (CTIT Technical Report Series; TR-CTIT-09-13).
@book{82ca08d93c494df8b73c8b6916824b5e,
title = "Adaptively Secure Computationally Efficient Searchable Symmetric Encryption",
abstract = "Searchable encryption is a technique that allows a client to store documents on a server in encrypted form. Stored documents can be retrieved selectively while revealing as little information as possible to the server. In the symmetric searchable encryption domain, the storage and the retrieval are performed by the same client. Most conventional searchable encryption schemes suffer from two disadvantages. First, searching the stored documents takes time linear in the size of the database, and/or uses heavy arithmetic operations. Secondly, the existing schemes do not consider adaptive attackers; a search-query will reveal information even about documents stored in the future. If they do consider this, it is at a significant cost to updates. In this paper we propose a novel symmetric searchable encryption scheme that offers searching at constant time in the number of unique keywords stored on the server. We present two variants of the basic scheme which differ in the efficiency of search and update. We show how each scheme could be used in a personal health record system.",
keywords = "Searchable Encryption, METIS-263829, IR-65475, EWI-15312, SCS-Cybersecurity, Efficient Update, Efficient Search",
author = "S. Sedghi and {van Liesdonk}, P. and J.M. Doumen and Hartel, {Pieter H.} and Willem Jonker",
note = "http://eprints.ewi.utwente.nl/15312",
year = "2009",
month = "4",
day = "27",
language = "Undefined",
series = "CTIT Technical Report Series",
publisher = "Distributed and Embedded Security (DIES)",
number = "TR-CTIT-09-13",

}

Sedghi, S, van Liesdonk, P, Doumen, JM, Hartel, PH & Jonker, W 2009, Adaptively Secure Computationally Efficient Searchable Symmetric Encryption. CTIT Technical Report Series, no. TR-CTIT-09-13, Distributed and Embedded Security (DIES), Enschede.

Adaptively Secure Computationally Efficient Searchable Symmetric Encryption. / Sedghi, S.; van Liesdonk, P.; Doumen, J.M.; Hartel, Pieter H.; Jonker, Willem.

Enschede : Distributed and Embedded Security (DIES), 2009. 17 p. (CTIT Technical Report Series; No. TR-CTIT-09-13).

Research output: Book/ReportReportProfessional

TY - BOOK

T1 - Adaptively Secure Computationally Efficient Searchable Symmetric Encryption

AU - Sedghi, S.

AU - van Liesdonk, P.

AU - Doumen, J.M.

AU - Hartel, Pieter H.

AU - Jonker, Willem

N1 - http://eprints.ewi.utwente.nl/15312

PY - 2009/4/27

Y1 - 2009/4/27

N2 - Searchable encryption is a technique that allows a client to store documents on a server in encrypted form. Stored documents can be retrieved selectively while revealing as little information as possible to the server. In the symmetric searchable encryption domain, the storage and the retrieval are performed by the same client. Most conventional searchable encryption schemes suffer from two disadvantages. First, searching the stored documents takes time linear in the size of the database, and/or uses heavy arithmetic operations. Secondly, the existing schemes do not consider adaptive attackers; a search-query will reveal information even about documents stored in the future. If they do consider this, it is at a significant cost to updates. In this paper we propose a novel symmetric searchable encryption scheme that offers searching at constant time in the number of unique keywords stored on the server. We present two variants of the basic scheme which differ in the efficiency of search and update. We show how each scheme could be used in a personal health record system.

AB - Searchable encryption is a technique that allows a client to store documents on a server in encrypted form. Stored documents can be retrieved selectively while revealing as little information as possible to the server. In the symmetric searchable encryption domain, the storage and the retrieval are performed by the same client. Most conventional searchable encryption schemes suffer from two disadvantages. First, searching the stored documents takes time linear in the size of the database, and/or uses heavy arithmetic operations. Secondly, the existing schemes do not consider adaptive attackers; a search-query will reveal information even about documents stored in the future. If they do consider this, it is at a significant cost to updates. In this paper we propose a novel symmetric searchable encryption scheme that offers searching at constant time in the number of unique keywords stored on the server. We present two variants of the basic scheme which differ in the efficiency of search and update. We show how each scheme could be used in a personal health record system.

KW - Searchable Encryption

KW - METIS-263829

KW - IR-65475

KW - EWI-15312

KW - SCS-Cybersecurity

KW - Efficient Update

KW - Efficient Search

M3 - Report

T3 - CTIT Technical Report Series

BT - Adaptively Secure Computationally Efficient Searchable Symmetric Encryption

PB - Distributed and Embedded Security (DIES)

CY - Enschede

ER -

Sedghi S, van Liesdonk P, Doumen JM, Hartel PH, Jonker W. Adaptively Secure Computationally Efficient Searchable Symmetric Encryption. Enschede: Distributed and Embedded Security (DIES), 2009. 17 p. (CTIT Technical Report Series; TR-CTIT-09-13).