Updatable Private Set Intersection: Extended Functionalities, Deletion, and Worst-Case Complexity
Saikrishna Badrinarayanan, Peihan Miao, Xinyi Shi, Max Tromanhauser, and Ruida Zeng
Overview | Building | Experiments | Contact | License | Citation
UPSI Revisited implements the Updatable Private Set Intersection (UPSI) protocol as detailed in our Asiacrypt 2024 paper. Private Set Intersection (PSI) enables two mutually distrusting parties, each holding a private set of elements, to compute the intersection of their sets without disclosing any additional information. Building upon the foundational work presented in PoPETS 2022, our UPSI Revisited project addresses several key limitations of existing UPSI protocols:
- Extended Functionalities: Unlike previous protocols that support only plain PSI, our implementation includes advanced functionalities such as PSI-Cardinality and PSI-Sum. Additionally, in the addition-only setting, we present Circuit-PSI functionality that outputs secret shares of the intersection.
- Support for Deletion Operations: Previous UPSI protocols were limited to the addition of elements to their existing sets and "weak deletions" (where parties can additionally delete their old elements every t days). Our work introduces the capability to arbitrarily delete elements, achieving semi-honest security in both the addition-only and addition-deletion settings.
- Optimized Worst-Case Complexity: Existing addition-only protocols either require both parties to learn the output or only achieve low amortized complexity and incur linear worst-case complexity. Our protocols ensure that both computation and communication complexities scale solely with the size of set updates rather than the entire sets (except for a polylogarithmic factor).
Practical Performance: We have implemented our UPSI protocols and benchmarked them against state-of-the-art PSI and extended functionality protocols. Our results demonstrate favorable performance, particularly when dealing with sufficiently large total set sizes, sufficiently small new updates, or operating within low-bandwidth network environments.
Warning
This repository is a research prototype written to demonstrate our UPSI protocol's performance and to showcase its capabilities. It is NOT intended to be considered as "production ready" and should only be used for experimental or research & development purposes.
The repository has been containerized using Docker. To pull the appropriate container:
docker pull ghcr.io/ruidazeng/upsi-revisited:latest
If you're using a standard environment (e.g. amd64
Intel-based systems), run:
docker run -it ghcr.io/ruidazeng/upsi-revisited:latest
Warning
If you run into an error RTNETLINK answers: Operation not permitted
, add --cap-add=NET_ADMIN
to the docker run
command.
For users operating on Apple Silicon Macs (arm64
) or other ARM-based architectures, it might be necessary to specify the platform explicitly to direct Docker to emulate the standard environments and architectures, ensure compatibility and allowing the container to run:
docker run --platform linux/amd64 -it ghcr.io/ruidazeng/upsi-revisited:latest
Once inside the container, you can run any of the commands outlined in the following sections.
If you don't want to use Docker, you can build the project yourself.
Important
The project should be built on Debian 10 (buster) to ensure dependencies will build without issue.
The build.sh script will handle installation of build dependencies (namely python, bazel, and emp-toolkit
). The UPSI library can then be built using the bazel endpoints:
# for the addition only cardinality, sum, and circuit updatable psi protocols
bazel build //upsi/addition:all
# for the addition & deletion cardinality and sum updatable psi protocols
bazel build //upsi/deletion:all
# for the addition only plain psi protocol
bazel build //upsi/original:all
# for the addition & deletion plain psi protocol
bazel build //upsi/deletion-psi:all
Before running experiments, use the setup
binary to generate encryption keys and mock input sets. By default, keys and input sets will be placed in out/
and data/
, respectively.
The protocols correspond to specific functionalities as outlined in the paper:
addition
: Addition-Only UPSI-Cardinalty/Sum/Circuit-PSIdeletion
: UPSI-Cardinalty/Sum with Addition and Deletionoriginal
: Addition-Only Plain UPSIdeletion-psi
: Plain UPSI with Addition and Deletion
For more details, refer to the corresponding sections in the paper:
addition
&original
: Section 3.2deletion
&deletion-psi
: Section 4.2
To explore the parameters for each protocol, use the --help
flag for the setup
binary as follows:
./bazel-bin/upsi/<protocol>/setup --help
The --func
flag specifies the functionality to be used in the experiment. The available values are:
-
PSI
: Plain PSI, allowing two parties to compute the intersection of their sets without revealing any additional information. -
CA
: PSI-Cardinality, which computes the size of the intersection between the two sets. -
SUM
: PSI-Sum, calculating the sum of values associated with the elements in the intersection. -
SS
: Circuit-PSI, outputting the secret shares (SS) of the intersection.
To replicate the fourth row in Table 2 (--start_size
parameter in the setup
binary to generate encrypted datasets that are used as the "carry over" from the
./bazel-bin/upsi/addition/setup --func=CA --days=1 --daily_size=64 --start_size=262080
Note that
To simplify the setup of network conditions for experiments, the network_setup.sh script is provided in the base directory. This script automates the configuration of network bandwidth and latency, simulating both LAN and WAN environments as described in Section 6.1 of the paper.
In Section 6.1, the paper explains the network conditions used for experiments:
- LAN Connection:
- RTT (Round Trip Time): 0.2 ms
- Bandwidth: 1 Gbps
- WAN Connection:
- RTT (Round Trip Time): 80 ms
- Bandwidth Options: 200 Mbps, 50 Mbps, and 5 Mbps
These settings follow the same settings as previous works and are critical for reproducing the results in Tables 2, 3, 4, and 5.
-
Enable a Specific Network Setting: Use the following command to set up a specific network condition. Replace
<latency>
with the RTT latency in milliseconds and<bandwidth>
with the desired (optional) max bandwidth in Mbps../network_setup.sh on <latency> <bandwidth>
Example configurations:
-
LAN (1 Gbps, 0.2 ms RTT):
./network_setup.sh on 0.2 1000
-
WAN (200 Mbps, 80 ms RTT):
./network_setup.sh on 80 200
-
WAN (50 Mbps, 80 ms RTT):
./network_setup.sh on 80 50
-
WAN (5 Mbps, 80 ms RTT):
./network_setup.sh on 80 5
-
-
Disable Network Emulation: After completing the experiments under the specified network condition, disable the network emulation by running:
./network_setup.sh off
Once the encryption keys and data sets are generated, and the network is setup as desired, each party in the protocol can be run:
./bazel-bin/upsi/addition/run --party=1 --days=1 --func=CA
and
./bazel-bin/upsi/addition/run --party=0 --days=1 --func=CA
Note
You must run run --party=1
before run --party=0
as the first party will wait for connections on the specified port.
Or to run both parties, you can do:
./bazel-bin/upsi/addition/run --party=1 --days=1 --func=CA & ./bazel-bin/upsi/addition/run --party=0 --days=1 --func=CA
Important
If you've used --start_size
in the setup
command, you must include the
--trees
flag in run
to read and use the prepared state.
Below is a step-by-step example workflow to configure and run experiments under LAN and WAN conditions:
-
Run the Experiment on LAN (1 Gbps):
./network_setup.sh on 0.2 1000 ./bazel-bin/upsi/addition/run --party=1 --days=1 --func=CA ./bazel-bin/upsi/addition/run --party=0 --days=1 --func=CA ./network_setup.sh off
-
Run the Experiment on WAN (200 Mbps):
./network_setup.sh on 80 200 ./bazel-bin/upsi/addition/run --party=1 --days=1 --func=CA ./bazel-bin/upsi/addition/run --party=0 --days=1 --func=CA ./network_setup.sh off
-
Run the Experiment on WAN (50 Mbps):
./network_setup.sh on 80 50 ./bazel-bin/upsi/addition/run --party=1 --days=1 --func=CA ./bazel-bin/upsi/addition/run --party=0 --days=1 --func=CA ./network_setup.sh off
-
Run the Experiment on WAN (5 Mbps):
./network_setup.sh on 80 5 ./bazel-bin/upsi/addition/run --party=1 --days=1 --func=CA ./bazel-bin/upsi/addition/run --party=0 --days=1 --func=CA ./network_setup.sh off
More information for both the setup
and run
binaries can be found using the --help
flag.
Feel free to reach out to the authors for further inquiries or collaborations:
Name | Affiliation | Contact |
---|---|---|
Saikrishna Badrinarayanan | bsaikrishna7393 [at] gmail [dot] com |
|
Peihan Miao | Brown University | peihan_miao [at] brown [dot] edu |
Xinyi Shi | Brown University | xinyi_shi [at] brown [dot] edu |
Max Tromanhauser | Brown University | max_tromanhauser [at] brown [dot] edu |
Ruida Zeng | Brown University | ruida_zeng [at] brown [dot] edu |
This project is licensed under the Apache License 2.0.
To enable easy citation of your work, you can add a citation section like this:
If you find our work useful in your research or reference it in your publications, please consider citing it as follows:
@inproceedings{bmxtz2024upsi,
title={{UPSI Revisited: Updatable Private Set Intersection: Extended Functionalities, Deletion, and Worst-Case Complexity}},
author={Saikrishna Badrinarayanan and Peihan Miao and Xinyi Shi and Max Tromanhauser and Ruida Zeng},
booktitle={Advances in Cryptology -- ASIACRYPT 2024},
year={2024},
publisher={Springer},
url={https://eprint.iacr.org/2024/1446},
}