Private Stream Searching Toolkit

Package: privss-0.11.tar.gz
License: GPL
Developers: John Bethencourt, Brent Waters (advisory role)
Contact: bethenco@cs.berkeley.edu
Added to ACSC: July 21, 2006
Last updated: September 28, 2009

Description

This toolkit provides programs implementing a private stream searching scheme.

Suppose a client sends some search keywords to a server. The server checks some documents against the keywords and eventually sends back all the documents that matched. But the catch is that the client wants all this to take place without the server being able to learn what keywords they are interested in or which documents they end up with. These programs let you do that.

The scheme to accomplish all this is built upon the additive homomorphism of the Paillier cryptosystem. To build the programs in the toolkit, you will need to have libpaillier installed. You will also need to install the Integer Matrix Library (IML), which is used for the special linear algebra techniques of the private searching scheme (local copy: iml-1.0.3.tar.gz). IML in turn requires the ATLAS implementation of BLAS.

Documentation

To try out the tools, take a look at the quickstart tutorial. Also, man pages for each of the three programs in the toolkit are available online.

  • Quickstart Tutorial
  • privss-qcon – the program used to generate encrypted queries
  • privss-search – the program used to match encrypted queries against documents to generate encrypted results
  • privss-recon – the program used to recover the matching documents from encrypted results

Bugs and Limitations

Right now, you can easily perform simple searches like the one in the tutorial, but effectively performing larger-scale searches is an esoteric process. Setting up a search with privss-qcon requires specifying some parameters which will significantly affect the performance and correctness of the resulting search. Generally, the "lower" the values given, the more modest the resource consumption, but the greater the likelihood of false positives and overflow (which prevents the matching documents from being recovered at the end). However, the defaults should work fine if you just want to try out the toolkit and don’t care about space or doing large-scale searches.

I might someday get around to implementing a higher-level, more intuitive interface for setting the search parameters. Until then you can just try doing searches with the default parameters, or, if you’re adventurous, try to figure out how to set them well for your application.

Papers

The toolkit implements the algorithms of the following paper.