Percy++ is an implementation of Private Information Retrieval (PIR) protocols in C++. These are the protocols described in the paper:
Ian Goldberg. Improving the Robustness of Private Information Retrieval. Proc. of 2007 IEEE Symposium on Security and Privacy (Oakland 2007), May 2007.
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:
- k-out-of-l
- 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.).
- t-private
- No coalition of up to t servers receives any information at all about the block you are interested in.
- v-Byzantine-robust
- 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.
- τ-independent
- 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 - floor(sqrt(k*(t+τ)))
Percy++ is written entirely in C++, using Victor Shoup's NTL library. You will need to install that library before you can use Percy++. In addition, if you tell NTL to use the GMP library when you install it, Percy++'s calculations will be faster.