Welcome to the resource topic for 2024/1560
Title:
Revisiting Shuffle-Based Private Set Unions with Reduced Communication
Authors: Jiseung Kim, Hyung Tae Lee, Yongha Son
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}.
ePrint: https://eprint.iacr.org/2024/1560
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .