Percy++ is an implementation of the Private Information Retrieval (PIR) protocols from the papers:
- Ian Goldberg. Improving the Robustness of Private Information Retrieval. Proc. of 2007 IEEE Symposium on Security and Privacy (Oakland 2007), May 2007.
- Ryan Henry, Femi Olumofin, Ian Goldberg. Practical PIR for Electronic Commerce. 18th ACM Conference on Computer and Communications Security, October 2011.
- C. Devet, I. Goldberg, and N. Heninger. Optimally Robust Private Information Retrieval. 21st USENIX Security Symposium, August 2012.
Briefly, private information retrieval is the task of fetching a block of data from a database server (or group of distributed servers) without the server(s) learning which block it was that you were interested in.
These protocols provide t-private v-Byzantine-robust τ-independent k-out-of-l private information retrieval. This means:
- there are l distributed database servers, and we only need to receive replies from k of them (the rest might be down, overloaded, unreachable, etc.)
- no coalition of up to t servers receives any information at all about the block you are interested in
- up to v of the servers that do reply might give incorrect answers; we will want to detect which servers did that, and to determine the correct database block
- the database is split between the servers so that no coalition of up to τ of them can determine the contents of the database itself (τ=0 means all the servers just have a complete copy of the database)
All of the above are "information-theoretic"; that is, the protections hold, even if the servers have unlimited computational power. We can also optionally add l-computationally-private to the list of properties. This gives "hybrid" protection against coalitions of larger than t servers; with this option enabled, coalitions of up to t servers still get no information at all about your query, but even if all l servers collude, they would still have to break a cryptographic problem in order to learn your query.
Any choice of t, v, τ, k and l will work, so long as they satisfy the following conditions:
- They are all integers.
- 0 < t <= t + τ < k <= l
- 0 <= v < k - t - τ - 1
Percy++ is written entirely in C++, using Victor Shoup's NTL library.