Multi-party Private Set Union

Environment

This code and following instructions is tested on Ubuntu 20.04, with g++ 11.4.0 and CMake 3.22.2

Requirement

• volepsi (commit 63990d8b873622844bb0ac588ab19d2ca66f062e) link
• OpenSSL
• OpenMP

Compilation

Install volepsi

Note that we need to install volepsi into the directory of MPSU

# in MPSU
git clone https://github.com/Visa-Research/volepsi.git
cd volepsi
git checkout 63990d8b873622844bb0ac588ab19d2ca66f062e

# compile and install volepsi
python3 build.py -DVOLE_PSI_ENABLE_BOOST=ON -DVOLE_PSI_ENABLE_GMW=ON -DVOLE_PSI_ENABLE_CPSI=OFF -DVOLE_PSI_ENABLE_OPPRF=OFF
python3 build.py --install=../libvolepsi
cp out/build/linux/volePSI/config.h ../libvolepsi/include/volePSI/

Compile and Install elgamal_openssl

Note that we need to install ecelgamal into the directory of MPSU

# in MPSU
mkdir -p libelgamal/lib
cd elgamal_openssl
mkdir build && cd build
cmake .. -DCMAKE_INSTALL_PREFIX=../../libecelgamal/lib
make
make install

Compile MPSU

# in MPSU
mkdir build && cd build
cmake ..
make

Running the code

Network setup

# for LAN setup
./sn.sh on 0.02 10000
# for WAN setup
./sn.sh 80 400
# turn off
./sn.sh off

Running MPSU experiment

Compute PSU of 3 parties each with set size $2^{14}$ using 4 threads.

cd build
# run
./main [num party] [num element]

You can substitute corresponding experiment number into [num party] and [num element]

For example, here is the code to test MPSU performance on 4 parties and 256 elements:

./main 4 256

Benchmark Run

We've run this code on a single server with AMD EPYC 74F3 processors and 256 GB of RAM. Here is the benchmark result

	Set size	$n=3$	$n=4$	$n=6$	$n=8$
LAN	$2^8$	0.15	0.26	0.53	0.90
	$2^{10}$	0.35	0.49	2.02	3.44
	$2^{12}$	2.17	3.74	7.88	13.49
	$2^{14}$	8.28	14.553	31.45	53.458
	$2^{16}$	32.28	57.31	121.80	211.95
WAN	$2^8$	1.03	1.50	3.90	6.66
	$2^{10}$	2.74	4.51	8.27	11.51
	$2^{12}$	5.28	8.73	15.47	24.45
	$2^{14}$	12.88	21.20	41.36	67.67
	$2^{16}$	38.62	66.29	139.22	239.35
Communication	$2^8$	0.16	0.34	0.89	1.69
	$2^{10}$	0.64	1.35	3.54	6.77
	$2^{12}$	2.58	5.41	14.18	27.07
	$2^{14}$	10.31	21.66	56.72	108.28
	$2^{16}$	41.25	86.63	226.88	433.13