Privacy-preserving set intersection


This is a C++ implementation of the FNP privacy-preserving set intersection protocol, originally invented by Freedman, Nissim and Pinkas in 2004, with security improvements later made by Nojima in 2008.


Download from this link


What is a privacy-preserving set intersection protocol?


With FNP protocol, you can compute set intersection between two parties without disclosing any element to the other party.  The FNP protocol belongs to the family of cryptographic protocol; it is specifically optimized to set intersection computation, thus it is believed to be much faster than more general-purpose cryptographic protocols.  The protocol also has parallelism built into its design, hence you can exploit modern multi-core processors for shorter computation time.  FNP uses the mathematical properties of homomorphic cryptosystem, which can mix and concatenate encrypted messages without knowing its content.


A toolchain and library for privacy-preserving set intersection


It comes with rudimentary command-line interface: client, server, and key-generation tool.  Extension and reuse is possible through C++ interfaces. The implementation is fully thread-aware and multi-core ready, thus computation time can be shortened by modern many-core machines.  We have verified significant performance gains with quad-core Xeons and Opterons, through the use of bucket allocation in the algorithm.


For homomorphic encryption and decryption, both modified ElGamal cryptosystem and Paillier cryptosystem have been implemented on top of gmp.  And yes, the source of randomness is always a headache for cryptosystem implementers; we have keyboard, file and network packet as the sources of entropy.


It requires OpenSSL, gmp, gmpxx, boost, pthread, and pcap to build.  It currently runs on Linux.


Operation


We assume that the mutually untrusting two parties are acting as a server and a client, each having a set of secret in a file.


The public key of clients should be stored in the server's elgamal_keystore (or paillier_keystore, depending on the cryptosystem you have chosen).  See fnp-keygen(1) for details on key generation.  The server is assumed to know client's public keys.


Typically, you start with customizing /usr/local/share/fnp/fnp-serverd.  There you define lots of details, e.g., location of secret set, crypto algorithm, port number, network interface etc.  See fnp-serverd(1) man page for more details.


After firing up the server, you invoke fnp-client(1) to compute set intersection among two secret sets.  Cryptographic protocol computes and emits matching elements between two parties.  See the man page for options.


Acknowledgments


The research and development of this particular implementation has been funded by the National Institute of Information and Communications Technology (NICT), Japan.  The accompanying MTN library, which is essential for this software, has been generously made available by Solution Crew, Inc.


References


Michael J. Freedman, Kobbi Nissim, and Benny Pinkas, "Ecient Private Matching and Set Intersection", Eurocrypt 2004.


Ryo Nojima and Youki Kadobayashi, "On the Security and the Performance of a Practical Two-Party 

Set-Intersection Protocol", SCIS 2008.


P. Paillier, "Public-Key Cryptosystems Based on Composite Degree Residue Classes", Eurocrypt'99, pp.223-238, 1999. 

SourceForge.net Logo