论文标题
用于分配问题的可验证多方计算求解器，并应用于空中交通管理
A Verifiable Multiparty Computation Solver for the Assignment Problem and Applications to Air Traffic Management
论文作者
论文摘要
在许多应用程序字段中，分配问题是一个必不可少的问题，并且经常用于优化资源使用情况。该问题已被充分理解，并且存在各种有效的算法来解决该问题。但是，目前尚不清楚通过利用比基于MPC的单纯形求解器的线性程序来利用更有效的解决方案策略来实现基于多方计算（MPC）的隐私实现的实践绩效。我们通过实施和比较不同的优化MPC算法来解决这个问题，以解决合理问题大小的分配问题。我们的经验方法揭示了基于MPC的优化的各种见解，与已知的基于单纯形的方法相比，我们测量了显着的（50倍）的速度。此外，我们还通过通过非交互性零知识证明来使结果可以公开验证来研究引入的间接费用。通过利用现代证明系统，与先前建议的方法以及紧凑的证明大小相比，我们还实现了明显的加速和验证时间。
The assignment problem is an essential problem in many application fields and frequently used to optimize resource usage. The problem is well understood and various efficient algorithms exist to solve the problem. However, it was unclear what practical performance could be achieved for privacy preserving implementations based on multiparty computation (MPC) by leveraging more efficient solution strategies than MPC based simplex solvers for linear programs. We solve this question by implementing and comparing different optimized MPC algorithms to solve the assignment problem for reasonable problem sizes. Our empirical approach revealed various insights to MPC based optimization and we measured a significant (50x) speedup compared to the known simplex based approach. Furthermore, we also study the overhead introduced by making the results publicly verifiable by means of non-interactive zero-knowledge proofs. By leveraging modern proof systems we also achieve significant speedup for proof and verification times compared to the previously proposed approaches as well as compact proof sizes.
