Private Stream Searching Toolkit
|Developers:||John Bethencourt, Brent Waters (advisory role)|
|Added to ACSC:||July 21, 2006|
|Last updated:||September 28, 2009|
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.
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.
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.
The toolkit implements the algorithms of the following paper.
New Techniques for Private Stream Searching
ACM Transactions on Information and System Security (TISSEC) 12 (3), January 2009.