Paper 2024/1560

Revisiting Shuffle-Based Private Set Unions with Reduced Communication

Abstract

A Private Set Union (PSU) allows two parties having sets $X$ and $Y$ to securely compute the union $X \cup Y$ while revealing no additional information. Recently, there have been proposed so-called shuffle-based PSU protocols due to Garimella et. al. (PKC'21) and Jia et. al. (USENIX'22). Except a few base oblivious transfers, those proposals are fully based on symmetric key primitives and hence enjoy quite low computation costs. However, they commonly have drawbacks on large communication cost of $O(\ell n\log n)$ with input set size $n$ and $\ell \ge O(\lambda + \log n)$ where $\lambda$ is a statistical security parameter. We propose two optimizations for each work that reduce communication cost while maintaining strength in computation cost; the first one optimizes Garimella et. al. to have $O(\ell n + n \log n)$, and the second one optimizes Jia et. al. by reducing the concrete value of $\ell$ by $\log n$. Concretely, the first (second, resp) optimization provides $3.3 - 3.9$x ($1.7 - 1.8$x, resp) lower communication input set sizes $n = 2^{16} - 2^{20}$. We demonstrate by comprehensive analysis and implementation that our optimization leads to better PSU protocol, compared to the state-of-the-art proposal of Zhang et. al. (USENIX'23) as well as previous shuffle-based PSUs. As a concrete amount of improvement, we see $1.4-1.5$x speed up for $100$Mbps network, and $1.8-2.2$x speed up for $10$Mbps network on input set sizes $n = 2^{16} - 2^{20}$.