1CWI, Amsterdam, The Netherlands. E-mail: hofheinz@cwi.nl2IKS, Universität Karlsruhe, Karlsruhe, Germany. E-mail: muellerq@ira.uka.de3MMCI, Saarland University, Saarbrücken, Germany. E-mail: unruh@mmci.uni-saarland.de
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.