Searching Keywords with Wildcards on Encrypted Data

S. Sedghi, Peter van Liesdonk, S.I. Nikova, Pieter H. Hartel, Willem Jonker

Research output: Book/ReportReportProfessional

55 Citations (Scopus)
759 Downloads (Pure)


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 ``$\star$'' (or wildcard) entries. Decryption is possible as long as these tuples agree on every position except where a ``$\star$'' occurs. These schemes are useful for a variety of applications: they can be used as 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 languageUndefined
Place of PublicationEnschede
PublisherCentre for Telematics and Information Technology (CTIT)
Number of pages13
Publication statusPublished - 8 Apr 2010

Publication series

NameCTIT Technical Report Series
PublisherCentre for Telematics and Information Technology, University of Twente
ISSN (Print)1381-3625


  • Pairing Based Cryptography
  • PEKS
  • SCS-Cybersecurity
  • METIS-270786
  • IR-70901
  • EWI-17789
  • Hidden Vector Encryption
  • Searchable Encryption

Cite this