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


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
Number of pages16
ISBN (Electronic)978-3-642-15317-4
ISBN (Print)978-3-642-15316-7
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
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference7th international Conference on Security and Cryptography for Networks, SCN 2010
Abbreviated titleSCN


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


Dive into the research topics of 'Searching Keywords with Wildcards on Encrypted Data'. Together they form a unique fingerprint.

Cite this