On the Necessity of Rewinding in Secure Multiparty Computation

Michael Backes, Jörn Müller-Quade, and Dominique Unruh.
in Theory of Cryptography, Proceedings of TCC 2007, Lecture Notes in Computer Science vol. 4392, Springer-Verlag, pp. 157-174, March 2007. Preprint on IACR ePrint 2006/315.

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.

Files available online

This publication is accompanied by links to downloadable versions of this publication. These documents do not necessarily correspond exactly to the cited version. Instead, in most cases full, updated or preliminary versions are provided. For access to the official version, follow the "Official version" link to the publishers site.

Slides used in my talks are available upon personal request, as long as you agree not to disseminate them to a wider audience or make them available online. If in doubt, please ask.