International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Privacy-Enhanced Searches Using Encrypted Bloom Filters

Steven M. Bellovin
William R. Cheswick
Search ePrint
Search Google
Abstract: It is often necessary for two or more or more parties that do not fully trust each other to selectively share data. We propose a search scheme based on Bloom filters and Pohlig-Hellman encryption. A semi-trusted third party can transform one party's search queries to a form suitable for querying the other party's database, in such a way that neither the third party nor the database owner can see the original query. Furthermore, the encryption keys used to construct the Bloom filters are not shared with this third party. Provision can be made for third-party ``warrant servers'', as well as ``censorship sets'' that limit the data to be shared.
  title={Privacy-Enhanced Searches Using Encrypted Bloom Filters},
  booktitle={IACR Eprint archive},
  keywords={applications / encrypted search, pohlig-hellman, group ciphers},
  note={under submission 12449 received 1 Feb 2004},
  author={Steven M. Bellovin and William R. Cheswick},