LEAP: A Fast, Lattice-based OPRF With Application to Private Set Intersection

Table 2: Preprocessing Complexity

Generated using the files in leap/tests/baseOT. The number of iterations can
be adjusted in leap/tests/baseOT/iter.h. The binaries will be in
tests once built.

Table 3: OPRF Communication and Computation Complexity

Generated using leap/tests/oprf-ref.cpp. The output includes the PRF output to verify correctness and hashing the OPRF output to remove the algebraic structure.
IP and port are hardcoded in the file for a simpler user interface.

Table 4: PSI computation/communication complexity

Generated using leap/tests/test-psi.cpp. The concrete calls are (in two
seperate terminals, from the build folder):

• leap/tests/test-psi 0 127.0.0.1 12345 20 and leap/tests/test-psi 1 127.0.0.1 12345 1
• leap/tests/test-psi 0 127.0.0.1 12345 20 and leap/tests/test-psi 1 127.0.0.1 12345 10
• leap/tests/test-psi 0 127.0.0.1 12345 24 and leap/tests/test-psi 1 127.0.0.1 12345 15

Build Instructions

mkdir build && cd build && cmake .. && make -j

Requirements

libOTe

Installed with python3 build.py --boost -DENABLE_SIMPLESTOT_ASM=ON -DENABLE_MR_KYBER=ON -DENABLE_IKNP=ON -DENABLE_SILENTOT=ON -DENABLE_SOFTSPOKEN_OT=ON -DENABLE_PIC=ON -D FETCH_AUTO=true --relic --install --sudo
Tested with release 2.1.0.

AVX2 instructions

Necessary.

Acknowledgements

This project depends or references a number of other projects:

• SPRING code used as a base for the implementation
• libOTe Release 2.1.0 for KyberOT
• Falcon's NTT implementation, used as a base for our more flexible NTT implementation
• Cuckoo Filter implementation for
  the PSI implementation
• SHAKE256 implementation