Percy++ / PIR in C++ Ian Goldberg <email@example.com> Casey Devet <firstname.lastname@example.org> Wouter Lueks <email@example.com> Ann Yang <firstname.lastname@example.org> Paul Hendry <email@example.com> Ryan Henry <firstname.lastname@example.org> Version 1.0: 2014-10-17 About Percy++ ------------- 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 tau-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 tau-independent: the database is split between the servers so that no coalition of up to tau of them can determine the contents of the database itself (tau=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, tau, k and l will work, so long as they satisfy the following conditions: - They are all nonnegative integers. - 0 < t <= t + tau < k <= l - 0 <= v < k - t - tau - 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. Building and Using Percy++ -------------------------- Percy++ uses the following libraries; you will need to install them before you can use Percy++: - NTL (http://www.shoup.net/ntl/) - Socket++ (http://www.linuxhacker.at/socketxx/) - libgcrypt (http://www.gnu.org/software/libgcrypt/) If Symmetric PIR support is desired, then the following additional libraries are required: - PBC (http://crypto.stanford.edu/pbc/) - PBCWrapper and PolyCommit (see below) In addition, if you tell NTL to use the GMP library when you install it, Percy++'s calculations will be faster. Percy++ assumes that NTL headers are located in /usr/local/include/NTL, and that the above libraries are located in /usr/local/lib. If this is not the case, you should edit the Makefile accordingly. If you are building on a 32-bit machine, set BIT32_SUPPORT to true in the Makefile. (Many parts of Percy++ are considerably faster on 64-bit machines.) Once the libraries are installed, running "make" should build the programs pirclient, pirserver, agclient, agserver, hybridclient, hybridserver, and splitdatabase. The *client and *server programs are sample frontends to the Percy++ library, meant primarily as a demonstration. Usage information can be obtained by running the commands with no arguments. The pirclient/pirserver pair implement information-theoretic PIR, as presented in the above papers [Goldberg 2007], [Henry et al. 2011], [Devet et al. 2012]. To overwrite the default value of h (the minimum number of honest servers), set the environment variable PIRC_H to be the desired value. The agclient/agserver pair implement computational PIR, as presented in [Aguilar Melchor and Gaborit 2007]. The hybridclient/hybridserver pair implement a hybrid information-theoretic/computation PIR, as presented in [Devet and Goldberg 2014]. The database is kept in a single file called "database". You can populate that file however you like; copying some amount of data from /dev/urandom is fine. The runtest and runtestset script are powerful wrappers that allow you to run tests on large numbers of combinations of modes and parameters, and gather detailed timing information. For more information about running these programs, run them with no arguments. To try the tau-independence property, you will need to split the database file into l pieces using the splitdatabase command (run it with no arguments to see its invocation options). For example, running "./splitdatabase database 1 5" will split the database into 5 files, named database.1, database.2, etc., with 1-independence. That is, no single database server could determine the contents of the database, but more than one could. Note that this is entirely separate from the t parameter, which controls how many servers can collude without being able to learn the value of your query (as opposed to the contents of the database). Then using the "-t 1" option to runtest (the parameter after -t is the value of tau) will test tau-independence. To try symmetric PIR, first ensure that SPIR_SUPPORT is set to 'true' in the Makefile, and additionally that PBCWrapper and PolyCommit (available in a separate package from Percy++) are located in the same directory as the percy diretory. To try SPIR, run pirclient and pirserver with the additional option '-Z polycommit.params'. Note that using symmetric PIR is much more computationally expensive than not using it. The server can distribute its computation over a group of worker servers. This is done by running the workers and then running pirserver_master with the correct information. (Use "make pirserver_master" to build this program. See the usage message for pirserver_master for more). The server can also use threading to distribute its computation. This can be done using the -T tag for pirserver. (See the usage message for pirserver for more details.) Feel free to send question, bug reports, patches, etc. to Ian Goldberg <email@example.com>. Reed-Solomon Decoding --------------------- The RSDecoder class is an implementation of Reed-Solomon decoding. We have implemented many decoding algorithms, including the algorithm described in the paper by Devet, Goldberg and Heninger (listed above). For more information about the API of RSDecoder, see the doxygen-generated documentation. Changelog --------- Version 1.0 (2014-10-17): - Added API documentation. Install doxygen 1.8.x and use 'make docs' to create the documentation. - Significantly changed the API of the classes. See the documentation for details. - Changed to the usage of executables, including pirclient and pirserver. Run the executables with --help flag to see usage. - Implemented the computational PIR protocol by Aguilar Melchor and Gaborit (2007). See agclient and agserver executables. - Implemented the hybrid PIR protocol by Devet and Goldberg (2014). See hybridclient and hybridserver executables. - Added multiblock querying for Goldberg's IT-PIR protocol (modes GF28, GF216, ZZ_P). Can now request multiple blocks in a single query. Use --batch-query option of pirclient. - Implemented Strassen's fast matrix multiplication algorithm for server computation in Goldberg's IT-PIR protocol (modes GF28, GF216, ZZ_P), based on Lueks and Goldberg (2015). - Added statistics collection to the servers and clients. See usage messages of executables for details. - Replaced testclient script with runtest and runtestset scripts. Run these scripts with --help to see usage messages. Known bugs: SPIR support may not be working correctly in this version. The doxygen documentation is incomplete. Version 0.9 (2013-06-07): - Added support for PIR servers that use multiple worker hosts to do their computations faster, and/or use multiple threads or processes per host - Considerably cleaned up the APIs on the client and server sides - "make libs" will now build separate Percy++ client and server libraries for linking into your own programs - Removed variable-length arrays for compiler portability - Improved the speed of queries for multiple blocks in GF(2^8) - Added "-1 / --oneconn" option to pirserver to accept a single client connection and not fork (useful for debugging) Version 0.8 (2012-06-29): - Added support for Symmetric PIR, fast arithmetic in GF(2^16), and Chor et. al's lightweight protocol - Implemented many Reed-Solomon decoding algorithms, including Berlekamp-Welch, Cohn-Heninger Single-Polynomial Decoding, Cohn-Heninger Multi-Polynomial Decoding, a dynamic programming approach and a portfolio algorithm of all of the above. This allows for successful decoding with a higher number of Byzantine servers. - Modified command-line usage of testclient, pirclient and pirserver. - Improved testclient; testclient now kills pirserver processes after the test is completed. - Modified pirserver and pirclient to use sockets for communication; pirserver processes are now launched separately from pirclient. Version 0.7.1 (2007-06-17): (Based on patches from Len Sassaman <Len.Sassaman@esat.kuleuven.be>) Added support for *BSD stat(1) in testclient, and testclient now does additional sanity checks and auto-generates the test database if it doesn't exist (or isn't readable). Added the makefile argument "distclean" to clean up extraneous files. Utilities now display the current version number when given the argument --version. When recovering from Byzantine servers and HardRecover is invoked, a command-line message is displayed. Version 0.7 (2007-04-03): The Guruswami-Sudan implementation has been changed to a much more effecient algorithm. This saves about 70% of the runtime in the presence of Byzantine servers. Set the environment variable PIRC_NAIVE=1 to revert to the old algorithm for comparison. Version 0.6 (2007-03-14): Thanks to M. Jason Hinek <firstname.lastname@example.org>, the dependency on MuPAD has been removed. All computations are now done natively in C++ using NTL. Version 0.5 (2007-03-02): Initial release Copyright --------- Percy++ is covered by the following (GPL) license: Percy++ Copyright 2007,2012,2013,2014 Ian Goldberg <email@example.com>, Casey Devet <firstname.lastname@example.org>, Wouter Lueks <email@example.com>, Ann Yang <firstname.lastname@example.org>, Paul Hendry <email@example.com>, Ryan Henry <firstname.lastname@example.org> This program is free software; you can redistribute it and/or modify it under the terms of version 2 of the GNU General Public License as published by the Free Software Foundation. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. There is a copy of the GNU General Public License in the COPYING file packaged with this plugin; if you cannot find it, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA The ZZ_pXY.cc and ZZ_pXY.h files are adapted from files in version 5.4 of the NTL package by Victor Shoup <email@example.com>, with modifications by M. Jason Hinek <firstname.lastname@example.org> and Ian Goldberg <email@example.com>, and are also under the above GPL version 2 license. Portions of pirclient.cc and pirserver.cc are by Femi Olumofin <firstname.lastname@example.org>, under the same GPL version 2 license.