Skip to content
SpOT-Light: Lightweight Private Set Intersection from Sparse OT Extension (CRYPTO 2019)
C++ C CMake PowerShell
Branch: master
Clone or download
Latest commit 7cba0c4 Aug 21, 2019
Type Name Latest commit message Commit time
Failed to load latest commit information.
Tests sync May 28, 2019
TestsVS sync May 28, 2019
frontend low-spot update Aug 7, 2019
libOTe @ 8b4e2e2 clearing... Mar 17, 2018
libPSI Update CMakeLists.txt Aug 13, 2019
script Create setup_and_compile Aug 14, 2019
thirdparty Add files via upload Aug 13, 2019
.gitignore 3party Jul 30, 2018
.gitmodules 1st\ Nov 10, 2017
CMakeLists.txt manually include_directories("${BOOST_ROOT}") Aug 7, 2019
ExternalDependancies.props clearing... Mar 17, 2018 Update Aug 21, 2019
buildAll.ps1 1st\ Nov 10, 2017
copySourceToLinux.ps1 minor Apr 28, 2018
mainPSI.sln linux Mar 27, 2018

Sparse OT Extension & PSI

This is the implementation of our CRYPTO 2019 paper: SpOT-Light: Lightweight Private Set Intersection from Sparse OT Extension[ePrint].

Evaluating on a single server (2 36-cores Intel Xeon CPU E5-2699 v3 @ 2.30GHz and 256GB of RAM) with a single thread per party, each party has 2^20 items, our spot-low protocol requires 270 seconds and 63.1 MB , and our spot-fast protocol requires 25.6 seconds and 76.4 MB.


Clone project

git clone --recursive

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:

change ntl code
   struct MatPrime_crt_helper_deleter_policy {
      static void deleter(MatPrime_crt_helper *p) { MatPrime_crt_helper_deleter(p); }


   struct MatPrime_crt_helper_deleter_policy {
      static void deleter(MatPrime_crt_helper *p) {; }

In lip.h (line 645), change "class _ntl_general_rem_one_struct" to be "struct _ntl_general_rem_one_struct;".

Building the Project

After cloning project from git,

  1. build cryptoTools,libOTe, and libOPRF projects in order.
  2. add argument for bOPRFmain project (for example: -u)
  3. run bOPRFmain project
  1. make (requirements: CMake, Make, g++ or similar)
  2. for test: ./bin/frontend.exe -t

Running the code

The database is generated randomly. The outputs include the average online/offline/total runtime that displayed on the screen and output.txt.


-u		unit test which computes PSI of 2 paries, each with set size 2^8 in semi-honest setting
-n		log of set size (e.g. n=8 => setsize =2^8)
-N		set size
-echd	        evaluating DH-based PSI
                 -c: curve type (0: k283 vs 1: Curve25519)
-p              evaluating our protocols (0: `spot-fast` vs 1: `spot-low`)
-t		number of thread
-ip		ip address and port (eg.


1. Unit test:
./bin/frontend.exe -u
2. PSI:


./bin/frontend.exe -r 1 -echd -c 0 -n 8 -ip
& ./bin/frontend.exe -r 0 -echd -c 0 -n 8 -ip


./bin/frontend.exe -r 1 -n 8 -t 1 -p 0 -ip
& ./bin/frontend.exe -r 0 -n 8 -t 1 -p 0 -ip


./bin/frontend.exe -r 1 -n 8 -t 1 -p 1 -ip
& ./bin/frontend.exe -r 0 -n 8 -t 1 -p 1 -ip


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

You can’t perform that action at this time.