Polynomial Runtime and Composability

Polynomial Runtime and ComposabilityD. Hofheinz, D. Unruh, and J. Müller-Quade (Journal of Cryptology, 2012).  [publisher's version | eprint]

Abstract: We devise a notion of polynomial runtime suitable for the simulation-based security analysis of multi-party cryptographic protocols. Somewhat surprisingly, straightforward notions of polynomial runtime lack expressivity for reactive tasks and/or lead to an unnatural simulation-based security notion. Indeed, the problem has been recognized in previous works, and several notions of polynomial runtime have already been proposed. However, our new notion, dubbed reactive polynomial time is the first to combine the following properties:

We work in the Universal Composability (UC) protocol framework. We remark that while the UC framework already features a universal composition theorem, we develop new techniques to prove secure composition in case of reactively polynomial time protocols and attacks.