CryptoDB
Secure Stochastic Multi-party Computation for Combinatorial Problems and a Privacy Concept that Explicitely Factors out Knowledge about the Protocol
| Authors: | |
|---|---|
| Download: | |
| 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. |
BibTeX
@misc{eprint-2005-12490,
title={Secure Stochastic Multi-party Computation for Combinatorial Problems and a Privacy Concept that Explicitely Factors out Knowledge about the Protocol},
booktitle={IACR Eprint archive},
keywords={applications / arithmetic circuits, privacy concepts, combinatorial problems},
url={http://eprint.iacr.org/2005/154},
note={ msilaghi@fit.edu 13177 received 21 May 2005, last revised 28 Jan 2006},
author={Marius C. Silaghi and Gerhard Friedrich},
year=2005
}