Secure Stochastic Multi-party Computation for Combinatorial Problems

High levels of security often imply that the computation time should be inde-pendent of the value of involved secrets. When the expected answer of the solver is either a solution or unsatisable, then the previous assumption leads to algo-rithms that take always the computation time of the worst case. This is particularly disturbing for NP-hard combinatorial problems. In this work we start from the observation that sometimes (specially for hard problems) users nd it acceptable to receive as answer either a solution, the answer unsatisable or a failure with meaning don’t know. More exactly users accept incomplete solvers. As argued in [Sil05b], for certain problems privacy reasons lead users to prefer having an answer meaning don’t know even when the secure multi-party computation could have proven unsatisable (to avoid revealing that all alternatives are infeasible). While the solution proposed in [Sil05b] is slower than complete algorithms, here we show secure stochastic solutions that are faster than complete solvers, allowing to address larger problem instances.