Polynomial runtime in simulatability definitions^*

Issue title: 18th IEEE Computer Security Foundations Symposium (CSF 18)

Guest editors: J.D. Guttman

Article type: Research Article

Authors: Hofheinz, Dennis^a | Müller-Quade, Jörn^b | Unruh, Dominique^c

Affiliations: [a] CWI, Amsterdam, The Netherlands. E-mail: hofheinz@cwi.nl | [b] IKS, Universität Karlsruhe, Karlsruhe, Germany. E-mail: muellerq@ira.uka.de | [c] MMCI, Saarland University, Saarbrücken, Germany. E-mail: unruh@mmci.uni-saarland.de

Note: [*] A preliminary version of this paper appeared at [17].

Abstract: We elaborate on the problem of polynomial runtime in simulatability definitions for multi-party computation. First, the need for a new definition is demonstrated by showing which problems occur with common definitions of polynomial runtime. Then, we give a definition which captures in an intuitive manner what it means for a protocol or an adversary to have polynomial runtime. We show that this notion is suitable for simulatability definitions for multi-party computation. In particular, a composition theorem is shown for this notion.

Keywords: Multi-party computation, reactive simulatability, universal composability

DOI: 10.3233/JCS-2009-0354

Journal: Journal of Computer Security, vol. 17, no. 5, pp. 703-735, 2009