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 $$ with input set size $$ and $$ where $$ 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 $$, and the second one optimizes Jia et. al. by reducing the concrete value of $$ by $$. Concretely, the first (second, resp) optimization provides $$x ($$x, resp) lower communication input set sizes $$. 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 $$x speed up for $$Mbps network, and $$x speed up for $$Mbps network on input set sizes $$.