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.

• Casey Devet, Ian Goldberg, and Nadia Heninger. Optimally Robust Private Information Retrieval. 21st USENIX Security Symposium, August 2012.

• Carlos Aguilar Melchor and Philippe Gaborit. A Lattice-Based Computationally-Efficient Private Information Retrieval Protocol. WEWORC 2007, July 2007.

• Casey Devet and Ian Goldberg. The Best of Both Worlds: Combining Information-Theoretic and Computational PIR for Communication Efficiency. 14th Privacy Enhancing Technologies Symposium (PETS 2014), July 2014.

• Wouter Lueks, Ian Goldberg. Sublinear Scaling for Multi-Client Private Information Retrieval. 19th International Conference on Financial Cryptography and Data Security, January 2015.

Briefly, private information retrieval is the task of fetching a block of data from a database server (or a 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, so long as no more than t server are colluding to determine the client's query.

Any choice of t, v, τ, k and l will work, so long as they satisfy the following conditions:

• They are all nonnegative integers.
• 0 < t <= t + τ < k <= l
• 0 <= v < k - t - τ - 1

This library also supports "computational" PIR, in which there is a single server, and it cannot learn the contents of the query, but the scheme has no robustness. The security of this scheme relies on certain lattice-based cryptographic assumptions.

Finally, it support "hybrid" PIR, which combines an information-theoretic PIR scheme with a computational one in order to hedge against either the non-collusion assumption or the cryptographic assumption being violated.

Percy++ is written in C++, using Victor Shoup's NTL library.