  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.
