Welcome to the resource topic for 2005/154
Title:
Secure Stochastic Multi-party Computation for Combinatorial Problems and a Privacy Concept that Explicitely Factors out Knowledge about the Protocol
Authors: Marius C. Silaghi, 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.
ePrint: https://eprint.iacr.org/2005/154
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .