Multiparty Delegated Private Set Union With Efficient Updates on Outsourced Datasets

Private set union (PSU) has been an emerging topic in recent years due to its variety of applications. In particular, we are interested in deploying PSU in a cloud setting such that two players, the sender and the receiver, may outsource their sets to the cloud and update their sets. Later, the receiver can submit a union query to the cloud and learn the union of the sets without knowing the intersection. Of course, there is no need to restrict this scenario to only two players. A PSU operation that satisfies these properties is called updatable delegated PSU (UD-PSU). Despite the apparent usefulness of such operations, no related research, even on delegated PSU, has been conducted since Abadi et al. (TDSC 2017) posed the open problem of constructing a delegated PSU protocol. In this work, we address the above problem by presenting the first protocol for multiparty UD-PSU. Our starting point is Abadi et al.'s protocol (FC 2022) for multiparty updatable delegated private set intersection (a.k.a. Feather) built on a polynomial representation of the intersection of sets. The challenging hurdle for delegated PSU is to obtain a polynomial representation of the union of sets without revealing any information about the sets beyond the result. We develop a delegated PSU protocol by exploiting a rational polynomial representation. We then extend this basic protocol to support update operations, i.e., UD-PSU. Second, we improve the update efficiency of the resulting UD-PSU protocol to Õ(n log p), which works on polynomials of degree n over finite fields of order p. Finally, we implement our protocol in C++ and perform a comprehensive evaluation varying the cardinality of the sets and the number of players. Interestingly, the experimental results demonstrate that our protocol is comparable to Feather in overall performance. In particular, our update protocol shows an 8-12× improvement relative to Feather's update.