Eduardo Chielle (New York University Abu Dhabi), Michail Maniatakos (New York University Abu Dhabi)

A Private Set Intersection (PSI) protocol is a cryptographic method allowing two parties, each with a private set, to determine the intersection of their sets without revealing any information about their entries except for the intersection itself. While extensive research has focused on PSI protocols, most studies have centered on scenarios where two parties possess sets of similar sizes, assuming a semi-honest threat model.
However, when the sizes of the parties' sets differ significantly, a generalized solution tends to underperform compared to a specialized one, as recent research has demonstrated. Additionally, conventional PSI protocols are typically designed for a single execution, requiring the entire protocol to be re-executed for each set intersection. This approach is suboptimal for applications such as URL denylisting and email filtering, which may involve multiple set intersections of small sets against a large set (e.g., one for each email received).
In this study, we propose a novel PSI protocol optimized for the recurrent setting where parties have unbalanced set sizes. We implement our protocol using Levelled Fully Homomorphic Encryption and Cuckoo hashing, and introduce several optimizations to ensure real-time performance. By utilizing the Microsoft SEAL library, we demonstrate that our protocol can perform private set intersections in 20 ms and 240 ms on 10 Gbps and 100 Mbps networks, respectively.
Compared to existing solutions, our protocol offers significant improvements, reducing set intersection times by one order of magnitude on slower networks and by two orders of magnitude on faster networks.

View More Papers

ReDAN: An Empirical Study on Remote DoS Attacks against...

Xuewei Feng (Tsinghua University), Yuxiang Yang (Tsinghua University), Qi Li (Tsinghua University), Xingxiang Zhan (Zhongguancun Lab), Kun Sun (George Mason University), Ziqiang Wang (Southeast University), Ao Wang (Southeast University), Ganqiu Du (China Software Testing Center), Ke Xu (Tsinghua University)

Read More

TME-Box: Scalable In-Process Isolation through Intel TME-MK Memory Encryption

Martin Unterguggenberger (Graz University of Technology), Lukas Lamster (Graz University of Technology), David Schrammel (Graz University of Technology), Martin Schwarzl (Cloudflare, Inc.), Stefan Mangard (Graz University of Technology)

Read More

A Formal Approach to Multi-Layered Privileges for Enclaves

Ganxiang Yang (Shanghai Jiao Tong University), Chenyang Liu (Shanghai Jiao Tong University), Zhen Huang (Shanghai Jiao Tong University), Guoxing Chen (Shanghai Jiao Tong University), Hongfei Fu (Shanghai Jiao Tong University), Yuanyuan Zhang (Shanghai Jiao Tong University), Haojin Zhu (Shanghai Jiao Tong University)

Read More

Reinforcement Unlearning

Dayong Ye (University of Technology Sydney), Tianqing Zhu (City University of Macau), Congcong Zhu (City University of Macau), Derui Wang (CSIRO’s Data61), Kun Gao (University of Technology Sydney), Zewei Shi (CSIRO’s Data61), Sheng Shen (Torrens University Australia), Wanlei Zhou (City University of Macau), Minhui Xue (CSIRO's Data61)

Read More