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.
Category / Keywords: applications / arithmetic circuits, privacy concepts, combinatorial problems Date: received 21 May 2005, last revised 28 Jan 2006 Contact author: msilaghi at fit edu Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation 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. Version: 20060129:022430 (All versions of this report) Discussion forum: Show discussion | Start new discussion