Percy++ / PIR in C++ (Modified to accommodate unsynchronized databases)

Ian Goldberg <iang@cs.uwaterloo.ca>
Casey Devet <cjdevet@cs.uwaterloo.ca>
Paul Hendry <pshendry@uwaterloo.ca>
Ryan Henry <rhenry@cs.uwaterloo.ca>
Modifications by Giulia Fanti <gfanti@eecs.berkeley.edu>


Percy version 0.9: 2013-06-07


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.

    C. Devet, I. Goldberg, and N. Heninger.  Optimally Robust Private 
    Information Retrieval.  In 21st USENIX Security Symposium, 2012. 

The modifications to Percy++ in this repository enable one to do PIR 
over databases that are not identical. Identical databases have 
traditionally been a core assumption in multi-server PIR. The new 
modifications also enable a user to request multiple records in one 
round of PIR. These modifications are an implementation of the 
protocols in paper:

    G. Fanti and K. Ramchandran.  Efficient, Multi-Server Private 
    Information Retrieval over Unsynchronized Databases.  In Allerton
    Conference, 2015. 
    
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 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.  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, tau, k and l will work, so long as they satisfy the
following conditions:

- They are all integers.
- 0 < t <= t + tau < k <= l
- 0 <= v < k - t - tau - 1

Percy++ is written entirely 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.

Once the libraries are installed, running "make" should build three 
programs: pirclient, pirserver, and splitdatabase.

The pirclient and pirserver programs are sample frontends to the Percy++
library, meant primarily as a demonstration.  The pirclient program
takes as arguments:

   r = number of blocks
   s = words per block
   b = block size (bytes)
   w = word size (bits)
   l = number of servers
   k = number of servers that need to respond
   t = number of servers that can collude
 idx = indices of blocks to fetch (0-based)
 tau = tau-independence value of database shares
   u = maximum number of files that can be unsynchronized across servers
   e = expansion factor for synchronization bins
idxi = indices of blocks to fetch (0-based).
   
   

The pirclient program will write the blocks it computes to standard out.
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 pirserver program takes the following optional parameters:

   -n DBBYTES: use first DBBYTES of database (default: use entire file)
   -w WORDSIZE: use a word size of WORDSIZE bytes (default: 8)
   -b BLOCKSIZE: use block size of BLOCKSIZE bytes (default: optimal block size)
   -S SERVERID: use the specified server ID
   -p PORTNO: listen for connections on the specified port

For full command-line usage instructions, run pirclient or pirserver 
without parameters.

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 testclient script spawns l pirserver processes and one pirclient process
and attempts to query the database.  When pirclient is finished, the script
checks that the output indeed contains the requested database blocks.  For more
information about running testclient, run it with the --help flag set.

To try the tau-independence property, you will need to split the
database file into l pieces using the splitdatabase command.  Run
"./splitdatabase 1 5" to 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 running "./testclient 5 2 -t 1" (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 
'-s polycommit.params'; make sure that each server is provided a server ID with 
-S, as this is required for SPIR. 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.  (See the usage message
for pirserver_master and doc/distserver.txt 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 the above
address.


Reed-Solomon Decoding
---------------------

The RSDecoder class is an implementation of Reed-Solomon decoding.  We have
implemented many decoding algorithms, specifically the algorithm described in
the paper by Devet, Goldberg and Heninger (listed above).  For more information
about the API of RSDecoder, see doc/rsdecoder.txt.



Changelog
---------

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 <mjhinek@alumni.uwaterloo.ca>, 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 Ian Goldberg <iang@cs.uwaterloo.ca>
    Casey Devet <cjdevet@cs.uwaterloo.ca>
    Paul Hendry <pshendry@uwaterloo.ca>
    Ryan Henry <rhenry@cs.uwaterloo.ca>

    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 <victor@shoup.net>, with
modifications by M. Jason Hinek <mjhinek@alumni.uwaterloo.ca> and
Ian Goldberg <iang@cs.uwaterloo.ca>, and are also under the above GPL
version 2 license.  Portions of pirclient.cc and pirserver.cc are by
Femi Olumofin <fgolumof@cs.uwaterloo.ca>, under the same GPL version 2
license.