International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

On the Necessity of Rewinding in Secure Multiparty Computation

Authors:
Michael Backes
Jörn Müller-Quade
Dominique Unruh
Download:
URL: http://eprint.iacr.org/2006/315
Search ePrint
Search Google
Abstract: We investigate whether security of multiparty computation in the information-theoretic setting implies their security under concurrent composition. We show that security in the stand-alone model proven using black-box simulators in the information-theoretic setting does not imply security under concurrent composition, not even security under 2-bounded concurrent self-composition with an inefficient simulator and fixed inputs. This in particular refutes recently made claims on the equivalence of security in the stand-alone model and concurrent composition for perfect and statistical security (STOC'06). Our result strongly relies on the question whether every rewinding simulator can be transformed into an equivalent, potentially inefficient non-rewinding (straight-line) simulator. We answer this question in the negative by giving a protocol that can be proven secure using a rewinding simulator, yet that is not secure for any non-rewinding simulator.
BibTeX
@misc{eprint-2006-21806,
  title={On the Necessity of Rewinding in Secure Multiparty Computation},
  booktitle={IACR Eprint archive},
  keywords={foundations / Secure computation, information-theoretic security, black-box simulation, protocol composition},
  url={http://eprint.iacr.org/2006/315},
  note={ unruh@cs.uni-sb.de 13404 received 13 Sep 2006},
  author={Michael Backes and Jörn Müller-Quade and Dominique Unruh},
  year=2006
}