  Multi-party private set union (MPSU) protocol enables $m$ $(m > 2)$ parties,
each holding a set, to collectively compute the union of their sets without
revealing any additional information to other parties. There are two main
categories of MPSU protocols: The first builds on public-key techniques. All
existing works in this category involve a super-linear number of public-key
operations, resulting in poor practical efficiency. The second builds on
oblivious transfer and symmetric-key techniques. The only existing work in this
category is proposed by Liu and Gao (ASIACRYPT 2023), which features the best
concrete performance among all existing protocols, despite its super-linear
computation and communication. Unfortunately, it does not achieve the standard
semi-honest security, as it inherently relies on a non-collusion assumption,
which is unlikely to hold in practice. Therefore, the problem of constructing a
practical MPSU protocol based on oblivious transfer and symmetric-key
techniques in standard semi-honest model remains open. Furthermore, there is no
MPSU protocol achieving both linear computation and linear communication
complexity, which leaves another unresolved problem. In this work, we resolve
these two open problems. We propose the first MPSU protocol based on oblivious
transfer and symmetric-key techniques in the standard semi-honest model. This
protocol is $4.9-9.3 \times$ faster than Liu and Gao in the LAN setting.
Concretely, our protocol requires only $3.6$ seconds in online phase for 3
parties with sets of $2^{20}$ items each. We propose the first MPSU protocol
achieving both linear computation and linear communication complexity, based on
public-key operations. This protocol has the lowest overall communication costs
and shows a factor of $3.0-36.5\times$ improvement in terms of overall
communication compared to Liu and Gao.
