Searching Keywords with Wildcards on Encrypted Data

Saeed Sedghi, Peter van Liesdonk, Svetla Nikova, Pieter Hartel, Willem Jonker

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

Abstract

A hidden vector encryption scheme (HVE) is a derivation of identity-based encryption, where the public key is actually a vector over a certain alphabet. The decryption key is also derived from such a vector, but this one is also allowed to have "*" (or wildcard) entries. Decryption is possible as long as these tuples agree on every position except where a "*" occurs. These schemes are useful for a variety of applications: they can be used as a building block to construct attribute-based encryption schemes and sophisticated predicate encryption schemes (for e.g. range or subset queries). Another interesting application -- and our main motivation -- is to create searchable encryption schemes that support queries for keywords containing wildcards. Here we construct a new HVE scheme, based on bilinear groups of prime order, which supports vectors over any alphabet. The resulting ciphertext length is equally shorter than existing schemes, depending on a trade-off. The length of the decryption key and the computational complexity of decryption are both constant, unlike existing schemes where these are both dependent on the amount of non-wildcard symbols associated to the decryption key. Our construction hides both the plaintext and public key used for encryption. We prove security in a selective model, under the decision linear assumption.
Original languageEnglish
Title of host publicationSecurity and Cryptography for Networks
Subtitle of host publication7th International Conference, SCN 2010, Amalfi, Italy, September 13-15, 2010, Proceedings
EditorsJuan A. Garay, Roberto De Prisco
Place of PublicationBerlin
PublisherSpringer
Pages138-153
Number of pages16
ISBN (Electronic)978-3-642-15317-4
ISBN (Print)978-3-642-15316-7
DOIs
Publication statusPublished - 15 Sep 2010
Event7th international Conference on Security and Cryptography for Networks, SCN 2010 - Amalfi, Italy
Duration: 13 Sep 201015 Sep 2010
Conference number: 7

Publication series

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

Conference

Conference7th international Conference on Security and Cryptography for Networks, SCN 2010
Abbreviated titleSCN
CountryItaly
CityAmalfi
Period13/09/1015/09/10

Fingerprint

Cryptography
Computational complexity

Keywords

  • METIS-271072
  • EWI-18604
  • SCS-Cybersecurity
  • IR-73702

Cite this

Sedghi, S., van Liesdonk, P., Nikova, S., Hartel, P., & Jonker, W. (2010). Searching Keywords with Wildcards on Encrypted Data. In J. A. Garay, & R. De Prisco (Eds.), Security and Cryptography for Networks: 7th International Conference, SCN 2010, Amalfi, Italy, September 13-15, 2010, Proceedings (pp. 138-153). (Lecture Notes in Computer Science; Vol. 6280). Berlin: Springer. https://doi.org/10.1007/978-3-642-15317-4_10
Sedghi, Saeed ; van Liesdonk, Peter ; Nikova, Svetla ; Hartel, Pieter ; Jonker, Willem . / Searching Keywords with Wildcards on Encrypted Data. Security and Cryptography for Networks: 7th International Conference, SCN 2010, Amalfi, Italy, September 13-15, 2010, Proceedings. editor / Juan A. Garay ; Roberto De Prisco. Berlin : Springer, 2010. pp. 138-153 (Lecture Notes in Computer Science).
@inproceedings{3e4706aee57a4fcbb49605b0f5e628fc,
title = "Searching Keywords with Wildcards on Encrypted Data",
abstract = "A hidden vector encryption scheme (HVE) is a derivation of identity-based encryption, where the public key is actually a vector over a certain alphabet. The decryption key is also derived from such a vector, but this one is also allowed to have {"}*{"} (or wildcard) entries. Decryption is possible as long as these tuples agree on every position except where a {"}*{"} occurs. These schemes are useful for a variety of applications: they can be used as a building block to construct attribute-based encryption schemes and sophisticated predicate encryption schemes (for e.g. range or subset queries). Another interesting application -- and our main motivation -- is to create searchable encryption schemes that support queries for keywords containing wildcards. Here we construct a new HVE scheme, based on bilinear groups of prime order, which supports vectors over any alphabet. The resulting ciphertext length is equally shorter than existing schemes, depending on a trade-off. The length of the decryption key and the computational complexity of decryption are both constant, unlike existing schemes where these are both dependent on the amount of non-wildcard symbols associated to the decryption key. Our construction hides both the plaintext and public key used for encryption. We prove security in a selective model, under the decision linear assumption.",
keywords = "METIS-271072, EWI-18604, SCS-Cybersecurity, IR-73702",
author = "Saeed Sedghi and {van Liesdonk}, Peter and Svetla Nikova and Pieter Hartel and Willem Jonker",
year = "2010",
month = "9",
day = "15",
doi = "10.1007/978-3-642-15317-4_10",
language = "English",
isbn = "978-3-642-15316-7",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "138--153",
editor = "Garay, {Juan A.} and {De Prisco}, Roberto",
booktitle = "Security and Cryptography for Networks",

}

Sedghi, S, van Liesdonk, P, Nikova, S, Hartel, P & Jonker, W 2010, Searching Keywords with Wildcards on Encrypted Data. in JA Garay & R De Prisco (eds), Security and Cryptography for Networks: 7th International Conference, SCN 2010, Amalfi, Italy, September 13-15, 2010, Proceedings. Lecture Notes in Computer Science, vol. 6280, Springer, Berlin, pp. 138-153, 7th international Conference on Security and Cryptography for Networks, SCN 2010, Amalfi, Italy, 13/09/10. https://doi.org/10.1007/978-3-642-15317-4_10

Searching Keywords with Wildcards on Encrypted Data. / Sedghi, Saeed; van Liesdonk, Peter; Nikova, Svetla; Hartel, Pieter; Jonker, Willem .

Security and Cryptography for Networks: 7th International Conference, SCN 2010, Amalfi, Italy, September 13-15, 2010, Proceedings. ed. / Juan A. Garay; Roberto De Prisco. Berlin : Springer, 2010. p. 138-153 (Lecture Notes in Computer Science; Vol. 6280).

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

TY - GEN

T1 - Searching Keywords with Wildcards on Encrypted Data

AU - Sedghi, Saeed

AU - van Liesdonk, Peter

AU - Nikova, Svetla

AU - Hartel, Pieter

AU - Jonker, Willem

PY - 2010/9/15

Y1 - 2010/9/15

N2 - A hidden vector encryption scheme (HVE) is a derivation of identity-based encryption, where the public key is actually a vector over a certain alphabet. The decryption key is also derived from such a vector, but this one is also allowed to have "*" (or wildcard) entries. Decryption is possible as long as these tuples agree on every position except where a "*" occurs. These schemes are useful for a variety of applications: they can be used as a building block to construct attribute-based encryption schemes and sophisticated predicate encryption schemes (for e.g. range or subset queries). Another interesting application -- and our main motivation -- is to create searchable encryption schemes that support queries for keywords containing wildcards. Here we construct a new HVE scheme, based on bilinear groups of prime order, which supports vectors over any alphabet. The resulting ciphertext length is equally shorter than existing schemes, depending on a trade-off. The length of the decryption key and the computational complexity of decryption are both constant, unlike existing schemes where these are both dependent on the amount of non-wildcard symbols associated to the decryption key. Our construction hides both the plaintext and public key used for encryption. We prove security in a selective model, under the decision linear assumption.

AB - A hidden vector encryption scheme (HVE) is a derivation of identity-based encryption, where the public key is actually a vector over a certain alphabet. The decryption key is also derived from such a vector, but this one is also allowed to have "*" (or wildcard) entries. Decryption is possible as long as these tuples agree on every position except where a "*" occurs. These schemes are useful for a variety of applications: they can be used as a building block to construct attribute-based encryption schemes and sophisticated predicate encryption schemes (for e.g. range or subset queries). Another interesting application -- and our main motivation -- is to create searchable encryption schemes that support queries for keywords containing wildcards. Here we construct a new HVE scheme, based on bilinear groups of prime order, which supports vectors over any alphabet. The resulting ciphertext length is equally shorter than existing schemes, depending on a trade-off. The length of the decryption key and the computational complexity of decryption are both constant, unlike existing schemes where these are both dependent on the amount of non-wildcard symbols associated to the decryption key. Our construction hides both the plaintext and public key used for encryption. We prove security in a selective model, under the decision linear assumption.

KW - METIS-271072

KW - EWI-18604

KW - SCS-Cybersecurity

KW - IR-73702

U2 - 10.1007/978-3-642-15317-4_10

DO - 10.1007/978-3-642-15317-4_10

M3 - Conference contribution

SN - 978-3-642-15316-7

T3 - Lecture Notes in Computer Science

SP - 138

EP - 153

BT - Security and Cryptography for Networks

A2 - Garay, Juan A.

A2 - De Prisco, Roberto

PB - Springer

CY - Berlin

ER -

Sedghi S, van Liesdonk P, Nikova S, Hartel P, Jonker W. Searching Keywords with Wildcards on Encrypted Data. In Garay JA, De Prisco R, editors, Security and Cryptography for Networks: 7th International Conference, SCN 2010, Amalfi, Italy, September 13-15, 2010, Proceedings. Berlin: Springer. 2010. p. 138-153. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-642-15317-4_10