Private Set Intersection (PSI)
Faster Private Set Intersection Based on OT Extension
By Benny Pinkas, Thomas Schneider and Michael Zohner in USENIX Security Symposium 2014 , Benny Pinkas, Thomas Schneider, Gil Segev and Michael Zohner in USENIX Security Symposium 2015 , and Benny Pinkas, Thomas Schneider and Michael Zohner in ePrint . Please note that the code is currently being restructured and not all routines might work correctly. The PSI code is licensed under AGPLv3, see the LICENSE file for a copy of the license. The implementations for performing PSI on a sets of a billion elements can be found here.
- An implementation of different PSI protocols:
- the naive hashing solutions where elements are hashed and compared
- the server-aided protocol of 
- the Diffie-Hellman-based PSI protocol of 
- the OT-based PSI protocol of 
This code is provided as a experimental implementation for testing purposes and should not be used in a productive environment. We cannot guarantee security and correctness.
A Linux distribution of your choice (the code was developed and tested with recent versions of Ubuntu).
Install these packages with your favorite package manager, e.g,
sudo apt-get install <package-name>.
Building the Project
Clone a copy of the main git repository and its submodules by running:
git clone --recursive git://github.com/encryptogroup/PSI
Enter the Framework directory:
makein the root directory to compile all dependencies, tests, and examples and create the executables: psi.exe (used for benchmarking) and demo.exe (a small demonstrator for intersecting email addresses).
Please note that downloading this project as ZIP file will yield compilation errors, since the Miracl library is included as external project. To solve this, download the Miracl sources in commit version
cff161b (found here and extract the contents of the main folder in
src/externals/Miracl. Then, continue with steps 2 and 3.
Executing the Code
An example demo is included and can be run by opening two terminals in the root directory. Execute in the first terminal:
./demo.exe -r 0 -p 0 -f sample_sets/emails_alice.txt
and in the second terminal:
./demo.exe -r 1 -p 0 -f sample_sets/emails_bob.txt
This should print the following output in the second terminal:
Computation finished. Found 3 intersecting elements: Michael.Zohner@ec-spride.de Evelyne.Wagener@tvcablenet.be Ivonne.Pfisterer@mail.ru
These commands will run the naive hashing protocol and compute the intersection on the 1024 randomly generated emails in sample_sets/emails_alice.txt and sample_sets/emails_bob.txt (where 3 intersecting elements were altered). To use a different protocol, the ['-p'] option can be varied as follows:
-p 0: the naive hashing protocol
-p 1: the server-aided protocol of 
-p 2: the Diffie-Hellman-based PSI protocol of 
-p 3: the OT-based PSI protocol of 
For further information about the program options, run
Testing the Protocols
The protocols will automatically be tested on randomly generated data when invoking:
WARNING: Some tests can still fail since the code is currently being debugged.
Generating Random Email Adresses
Further random email adresses can be generated by navigating to
sample_sets/emailgenerator/ and invoking:
The generator uses the first names, family names, and email providers listed in the corresponding files in
sample_sets/emailgenerator/ as base for the generation.
 B. Pinkas, T. Schneider, M. Zohner. Faster Private Set Intersection Based on OT Extension. USENIX Security 2014: 797-812. Full version available at http://eprint.iacr.org/2014/447.
 B. Pinkas, T. Schneider, G. Segev, M. Zohner. Phasing: Private Set Intersection using Permutation-based Hashing. USENIX Security 2015. Full version available at http://eprint.iacr.org/2015/634.
 B. Pinkas, T. Schneider, M. Zohner. Scalable Private Set Intersection Based on OT Extension. Available at http://eprint.iacr.org/2016/930.
 S. Kamara, P. Mohassel, M. Raykova, and S. Sadeghian. Scaling private set intersection to billion-element sets. In Financial Cryptography and Data Security (FC’14) , LNCS. Springer, 2014.
 C. Meadows. A more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party. In IEEE S&P’86, pages 134–137. IEEE, 1986.