Conjunctive Wildcard Search over Encrypted Data

C.T. Bösch, Richard Brinkman, Pieter H. Hartel

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

44 Citations (Scopus)
20 Downloads (Pure)


Searchable encryption allows a party to search over encrypted data without decrypting it. Prior schemes in the symmetric setting deal only with exact or similar keyword matches. We describe a scheme for the problem of wildcard searches over encrypted data to make search queries more flexible, provide a security proof for our scheme and com- pare the computational, communication and space complexity with existing schemes. We develop an efficient scheme, using pseudorandom functions and Bloom filters, that supports wildcard searches over encrypted data. The scheme also supports conjunctive wildcard searches, efficient and secure updates and is more efficient than previous solutions. Besides, our construction is independent of the encryption method of the remote data and is practical to use in real world applications.
Original languageUndefined
Title of host publication8th VLDB Workshop on Secure Data Management, SDM 2011
EditorsM. Petkovic, Willem Jonker, W. Jonker
Place of PublicationBerlin
Number of pages14
ISBN (Print)978-3-642-23555-9
Publication statusPublished - Sept 2011
Event8th VLDB Workshop on Secure Data Management, SDM 2011 - Seattle, United States
Duration: 2 Sept 20112 Sept 2011
Conference number: 8

Publication series

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


Workshop8th VLDB Workshop on Secure Data Management, SDM 2011
Abbreviated titleSDM
Country/TerritoryUnited States


  • METIS-278760
  • IR-77961
  • Bloom filter
  • SCS-Cybersecurity
  • Wildcard
  • EWI-20436
  • Searchable Encryption

Cite this