Paper 2004/022

Privacy-Enhanced Searches Using Encrypted Bloom Filters

Steven M. Bellovin and William R. Cheswick

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.

Metadata
Available format(s)
PDF PS
Category
Applications
Publication info
Published elsewhere. under submission
Keywords
encrypted searchpohlig-hellmangroup ciphers
Contact author(s)
smb @ research att com
History
2004-02-01: received
Short URL
https://ia.cr/2004/022
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2004/022,
      author = {Steven M.  Bellovin and William R.  Cheswick},
      title = {Privacy-Enhanced Searches Using Encrypted Bloom Filters},
      howpublished = {Cryptology {ePrint} Archive, Paper 2004/022},
      year = {2004},
      url = {https://eprint.iacr.org/2004/022}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.