Private Set Intersection for Small Sets

This is the implementation of our CCS 2021 paper: Compact and Malicious Private Set Intersection for Small Sets[ePrint].

Installations

Clone project

git clone --recursive git@github.com:osu-crypto/MiniPSI.git

Quick Installation (Linux)

$ cd MiniPSI
$ bash buildAll.get

If you have any problem, see below.

Required libraries

C++ compiler with C++14 support. There are several library dependencies including Boost, Miracl, NTL with GMP, and libOTe. For libOTe, it requires CPU supporting PCLMUL, AES-NI, and SSE4.1. Optional: nasm for improved SHA1 performance. Our code has been tested on both Windows (Microsoft Visual Studio) and Linux. To install the required libraries:

• For building boost, miracl and libOTe, please follow the more instructions at libOTe. A quick try for linux: cd libOTe/cryptoTools/thirdparty/linux/, bash all.get, cd back to libOTe, cmake . and then make -j
• For NTL with GMP and gf2x, cd ./thirdparty/linux, and run all.get. Then, you can run cmake . in SpOT-PSI folder, and then make -j
• See here for full setup script

NOTE: if you meet problem with NTL, try to do the following and read Building and using NTL with GMP. If you see an error message cmd.exe not found, try to install https://www.nasm.us/

Building the Project

After cloning project from git,

Windows:

1. build cryptoTools, libOTe, libsodium, libPSI projects in order.
2. add argument for frontend project (for example: -t)
3. run frontend project

Linux:

1. make (requirements: CMake, Make, g++ or similar)
2. for test: ./bin/frontend.exe -t

Running the code

Flags:

-t: unit test which computes PSI of 2 paries, each with set size 2^8 in semi-honest setting

-n:log of receiver's set size (e.g. n=8 => setsize =2^8)

-m: log of sender's set size (e.g. n=8 => setsize =2^8)

-r: evaluating DH-based PSI

-e: evaluating JL10-based PSI

-i: evaluating our poly-based PSI

Examples:

1. Unit test:

./bin/frontend.exe -t

2. PSI:

DH-based PSI

./bin/frontend.exe -r 0 -n 10  & ./bin/frontend.exe -r 1 -n 10

JL10-based PSI

./bin/frontend.exe -e 0 -n 10  & ./bin/frontend.exe -e 1 -n 10

our protocol (Poly-based PSI)

./bin/frontend.exe -i 0 -n 10  & ./bin/frontend.exe -i 1 -n 10

Help

For any questions on building or running the library, please contact Ni Trieu at trieun at oregonstate dot edu