Computationally Efficient Searchable Symmetric Encryption

Peter van Liesdonk, S. Sedghi, J.M. Doumen, Pieter H. Hartel

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

114 Citations (Scopus)

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 the performance of 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 storage. We show how each scheme could be used in a personal health record system. Fulltext Preview
Original languageUndefined
Title of host publicationProceedings of the Seventh International Workshop on Secure Data Management, SDM 2010
EditorsWillem Jonker, M. Petkovic
Place of PublicationBerlin
PublisherSpringer
Pages87-100
Number of pages14
ISBN (Print)978-3-642-15545-1
DOIs
Publication statusPublished - 17 Sep 2010

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Number6358
Volume6358
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Keywords

  • METIS-271132
  • SCS-Cybersecurity
  • EWI-18809
  • IR-74619

Cite this

van Liesdonk, P., Sedghi, S., Doumen, J. M., & Hartel, P. H. (2010). Computationally Efficient Searchable Symmetric Encryption. In W. Jonker, & M. Petkovic (Eds.), Proceedings of the Seventh International Workshop on Secure Data Management, SDM 2010 (pp. 87-100). (Lecture Notes in Computer Science; Vol. 6358, No. 6358). Berlin: Springer. https://doi.org/10.1007/978-3-642-15546-8_7
van Liesdonk, Peter ; Sedghi, S. ; Doumen, J.M. ; Hartel, Pieter H. / Computationally Efficient Searchable Symmetric Encryption. Proceedings of the Seventh International Workshop on Secure Data Management, SDM 2010. editor / Willem Jonker ; M. Petkovic. Berlin : Springer, 2010. pp. 87-100 (Lecture Notes in Computer Science; 6358).
@inproceedings{0628c55f63774fabae5a8bfe6323f924,
title = "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 the performance of 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 storage. We show how each scheme could be used in a personal health record system. Fulltext Preview",
keywords = "METIS-271132, SCS-Cybersecurity, EWI-18809, IR-74619",
author = "{van Liesdonk}, Peter and S. Sedghi and J.M. Doumen and Hartel, {Pieter H.}",
note = "10.1007/978-3-642-15546-8_7",
year = "2010",
month = "9",
day = "17",
doi = "10.1007/978-3-642-15546-8_7",
language = "Undefined",
isbn = "978-3-642-15545-1",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
number = "6358",
pages = "87--100",
editor = "Willem Jonker and M. Petkovic",
booktitle = "Proceedings of the Seventh International Workshop on Secure Data Management, SDM 2010",

}

van Liesdonk, P, Sedghi, S, Doumen, JM & Hartel, PH 2010, Computationally Efficient Searchable Symmetric Encryption. in W Jonker & M Petkovic (eds), Proceedings of the Seventh International Workshop on Secure Data Management, SDM 2010. Lecture Notes in Computer Science, no. 6358, vol. 6358, Springer, Berlin, pp. 87-100. https://doi.org/10.1007/978-3-642-15546-8_7

Computationally Efficient Searchable Symmetric Encryption. / van Liesdonk, Peter; Sedghi, S.; Doumen, J.M.; Hartel, Pieter H.

Proceedings of the Seventh International Workshop on Secure Data Management, SDM 2010. ed. / Willem Jonker; M. Petkovic. Berlin : Springer, 2010. p. 87-100 (Lecture Notes in Computer Science; Vol. 6358, No. 6358).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Computationally Efficient Searchable Symmetric Encryption

AU - van Liesdonk, Peter

AU - Sedghi, S.

AU - Doumen, J.M.

AU - Hartel, Pieter H.

N1 - 10.1007/978-3-642-15546-8_7

PY - 2010/9/17

Y1 - 2010/9/17

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 the performance of 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 storage. We show how each scheme could be used in a personal health record system. Fulltext Preview

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 the performance of 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 storage. We show how each scheme could be used in a personal health record system. Fulltext Preview

KW - METIS-271132

KW - SCS-Cybersecurity

KW - EWI-18809

KW - IR-74619

U2 - 10.1007/978-3-642-15546-8_7

DO - 10.1007/978-3-642-15546-8_7

M3 - Conference contribution

SN - 978-3-642-15545-1

T3 - Lecture Notes in Computer Science

SP - 87

EP - 100

BT - Proceedings of the Seventh International Workshop on Secure Data Management, SDM 2010

A2 - Jonker, Willem

A2 - Petkovic, M.

PB - Springer

CY - Berlin

ER -

van Liesdonk P, Sedghi S, Doumen JM, Hartel PH. Computationally Efficient Searchable Symmetric Encryption. In Jonker W, Petkovic M, editors, Proceedings of the Seventh International Workshop on Secure Data Management, SDM 2010. Berlin: Springer. 2010. p. 87-100. (Lecture Notes in Computer Science; 6358). https://doi.org/10.1007/978-3-642-15546-8_7