|Description||The algorithms we propose here are simple but our contribution consists in identifying the simple guidelines required for a high level of privacy. Achieving the highest level of privacy for secrets used in a distributed computation implies that the distributed computation (steps) should be independent of the value of these secrets. When the expected answer of a constraint satisfaction solver is either a solution or no_solution, then the previous assumption leads to algorithms that take always the computation time of the worst case. This is particularly disturbing for such NP-hard problems.
In this work we start from the observation that sometimes (specially for hard problems) users find it acceptable to receive as result not only a solution or the answer no_solution but also a failure with meaning don’t know, or solutions proven optimal only within a subset of the problem space. More exactly, users accept incomplete solvers. It is argued in (Silaghi 2005b) that, 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 no solution (to avoid revealing that all alternatives are infeasible). While the solution proposed there is slower than complete algorithms, here we show secure incomplete solutions that are faster than complete solvers, allowing to address larger problem instances. We show that one can build time-aware instances where given a known amount of available time, we obtain an incomplete solver terminating in that time and offering a very high degree of privacy, namely non-uniform requested t-privacy.||en_US