Breaking Free: Efficient Multi-Party Private Set Union Without Non-Collusion Assumptions

多方私有集合并(MPSU)协议使得$m$个$(m>2)$持有集合的各方能够在不向其他方透露任何额外信息的情况下，集体计算出它们的集合的并集。MPSU协议有两个主要类别：第一个基于公钥技术。该类别中的所有现有工作都涉及超线性数量的公钥操作，导致实用效率较差。第二个基于无差别传输和对称密钥技术。该类别中唯一的现有工作是由Liu和Gao(ASIACRYPT 2023)提出的，尽管它具有超线性计算和通信，但在所有现有协议中具有最佳的具体性能。不幸的是，它没有实现标准的半诚实安全性，因为它本质上依赖于一个不太可能在实践中成立的非串通假设。因此，在标准的半诚实模型中，基于无差别传输和对称密钥技术构建实用的MPSU协议的问题仍然存在。此外，没有MPSU协议同时实现线性计算和线性通信复杂度，这留下了另一个未解决的问题。在本文中，我们解决了这两个开放性问题。我们提出了第一个基于无差别传输和对称密钥技术的标准半诚实模型下的MPSU协议。在局域网环境中，该协议比Liu和Gao快4.9-9.3倍。具体而言，我们的协议对于3个持有$2^{20}$个项的集合的方，在在线阶段只需要3.6秒。我们提出了第一个基于公钥操作实现线性计算和线性通信复杂度的MPSU协议。该协议具有最低的总通信成本，并且相对于Liu和Gao，总体通信成本方面的改进达到了3.0-36.5倍。

提出一个在标准半诚实模型下基于交互式无用信息传递和对称密钥技术的多方私有集合联合(MPSU)协议，以实现$m$个持有集合的参与方的集合并集计算，同时保证不泄露任何额外信息。同时，提出了实现线性计算和线性通信复杂度的MPSU协议，这是一个未解决的问题。

提出了一种基于交互式无用信息传递和对称密钥技术的MPSU协议，该协议在标准半诚实模型下实现了协议参与方的集合并集计算，并且保证不泄露任何额外信息。同时，提出了一种基于公钥操作的MPSU协议，实现了线性计算和线性通信复杂度。

该论文提出的基于交互式无用信息传递和对称密钥技术的MPSU协议比已有的方案具有更好的实际效率，并且在标准半诚实模型下实现了协议参与方的集合并集计算，保证了隐私安全。同时，该论文提出的基于公钥操作的MPSU协议实现了线性计算和线性通信复杂度，具有最低的通信成本，并且相比已有的方案在通信方面有了3.0-36.5倍的提升。

最近的相关研究包括基于公钥技术的MPSU协议和基于交互式无用信息传递和对称密钥技术的MPSU协议。其中，基于公钥技术的MPSU协议的相关研究包括：《Efficient Multi-party Set Union with Linear Communication》。基于交互式无用信息传递和对称密钥技术的MPSU协议的相关研究包括：《A Practical Multi-Party Private Set Intersection Protocol Based on Homomorphic Encryption》。