On the Communication Complexity of Secure Multi-Party Computation With Aborts

密码学的一个核心目标是安全的多方计算（MPC），其中$n$个参与方希望计算他们联合输入的函数，而不让任何一方了解其同伴的输入。不幸的是，众所周知，当大多数方是恶意的时，保证MPC输出传递给每个方是不可行的。实际上，当超过三分之一的方是恶意的时，通过点对点网络（即没有广播信道）运作的方甚至无法就输出达成一致（Lamport，Shostak和Pease，JACM 1980）。受点对点模型中的这种不可行性的启发，Goldwasser和Lindell（J. Cryptol 2005）引入了一种不需要协议达成一致的MPC定义，称为具有选择性中止的MPC。在这个定义下，任何一方都可以在检测到恶意行为时中止协议。他们表明，通过实现带有中止的广播功能，任何数量的恶意方都可以实现具有选择性中止的MPC。虽然具有中止的MPC模型多年来引起了广泛关注，但很少有人了解它在点对点网络上的通信复杂性。在这项工作中，我们研究了具有中止的MPC的通信复杂性，并在该模型中设计了几乎最优的通信效率协议。换句话说，我们证明了诚实方数量$h$，通信复杂度和协议的局部性之间的权衡。这里，局部性是每个方必须与之通信的同伴数量的限制。

研究MPC with abort模型下的通信复杂度问题，提出一种近乎最优的通信高效的协议。

通过研究MPC with abort模型下的通信复杂度，提出了一种近乎最优的通信高效的协议，该协议考虑了诚实方的数量、通信复杂度和协议的本地性之间的权衡。

论文提出的协议在通信复杂度方面接近最优，并且考虑了协议的本地性，实验结果表明该协议在实际应用中具有较好的性能。论文还提到了MPC with abort模型的历史和研究现状。

与该论文相关的研究包括Goldwasser和Lindell在2005年提出的MPC with abort模型，以及其它关于MPC with abort模型的研究，如通信复杂度、本地性等方面的研究。