Show simple item record

dc.contributor.authorSilaghi, M
dc.contributor.authorFriedrich, G
dc.contributor.authorYokoo, M
dc.contributor.authorZanker, M
dc.date.accessioned2017-09-06T13:19:34Z
dc.date.available2017-09-06T13:19:34Z
dc.date.issued2006
dc.identifier.urihttp://hdl.handle.net/10863/2757
dc.description.abstractThe 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
dc.language.isoenen_US
dc.publisherAAAIen_US
dc.titleSecure incomplete multi-party computation for distributed constraint problemsen_US
dc.typeBook chapteren_US
dc.date.updated2016-05-26T08:22:18Z
dc.publication.titleProceedings of the 7th International Workshop on Distributed Constraint Reasoning
dc.description.fulltextopenen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record