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倍。具体而言，我们的协议对于每个拥有$2^{20}$个项目的3个方在在线阶段只需要3.6秒。我们提出了第一个基于公钥操作实现线性计算和线性通信复杂度的MPSU协议。该协议具有最低的总体通信成本，并且在总体通信方面相对于Liu和Gao显示出3.0-36.5倍的改进。

解决问题：该论文试图解决MPSU协议中的两个问题，即基于公钥技术的效率低下和基于对称密钥技术的半诚实安全问题，以及线性计算和通信复杂度问题。

关键思路：该论文提出了两个MPSU协议，一个基于对称密钥技术解决半诚实安全问题，并且在标准半诚实模型下实现了线性计算和通信复杂度；另一个基于公钥技术解决线性计算和通信复杂度问题，实现了最低的通信成本。

其他亮点：该论文的第一个协议比现有的最佳协议快4.9-9.3倍，并在3个拥有2^20个项目的集合上仅需要3.6秒的在线阶段。该论文的第二个协议比现有的协议在通信成本方面提高了3.0-36.5倍。实验结果表明，两个协议在实践中具有可行性和高效性。论文未提供开源代码。

相关研究：该论文提到了基于公钥技术和对称密钥技术的MPSU协议，并指出现有的协议在效率和安全性方面存在问题。