Paper 2005/154

Secure Stochastic Multi-party Computation for Combinatorial Problems and a Privacy Concept that Explicitely Factors out Knowledge about the Protocol

Marius C. Silaghi and Gerhard Friedrich

Abstract

High levels of security often imply that the computation time should be independent of the value of involved secrets. When the expected answer of the solver is either a solution or unsatisfiable, then the previous assumption leads to algorithms 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 find it acceptable to receive as answer either a solution, the answer unsatisfiable or a failure with meaning don't know. More exactly users accept incomplete solvers. As argued in [Silaghi,Flairs 05], 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 unsatisfiable (to avoid revealing that all alternatives are infeasible). While the solution proposed there is slower than complete algorithms, here we show secure stochastic solutions that are faster than complete solvers, allowing to address larger problem instances. Two new refined concepts of privacy are introduced, namely 'requested t-privacy' that factors out treatment of knowledge of the protocol in t-privacy, and a slightly weaker version called 'non-uniform requested t-privacy'. In the last section we discuss arithmetic circuits for complete and stochastic solutions to constraint optimization problems.

Note: The section on Constraint Optimization is a September 2005 addition, extending the FIT technical report CS-2005-15 from July 19, 2005 (later further expanded in the 9th Symposium on AI and Math'06). On December 31, January 2, the section defining the refined privacy concepts is extended by replacing the name 'maximal t-privacy' with 'requested t-privacy', and adding the concept of 'non-uniform requested t-privacy'. On Jan 28, 2006 we added the explanation about how first-in-array constant round protocol can replace certain non-constant round versions.