Our goal in this work is to find a good and useful definition of polynomial-time for multi-party protocols in the UC setting that matches the intuition of what is feasible. A good definition should have the following properties:
* Flexibility: All "intuitively feasible" protocols and protocol tasks should be considered polynomial-time.
* Soundness: All "intuitively feasible" attacks (i.e., adversaries) should be considered polynomial-time.
* Completeness: Only "intuitively feasible" attacks should be considered polynomial-time. In particular, this implies that the security of protocols can be reduced to computational hardness assumptions.
* Composability: The induced security notion should support secure (universal) composition of protocols.
* Simplicity: The notion should be easy to formulate, and for all practical cases, it should be easy to decide whether a protocol or attack runs in polynomial time. The problem of finding a good definition of polynomial time in the UC framework has been considered in a number of works, but no definition satisfying the five above criteria had been found so far. This seemingly simple problem is surprisingly elusive and it is hard to come up with a definition that does not involve many technical artifacts. In this contribution, we give a definition of polynomial time for cryptographic protocols in the UC model, called reactively polynomial, that satisfies all five properties. Our notion is simple and easy to verify. We argue for its flexibility, completeness and soundness with practical examples that are problematic with previous approaches. We give a very general composition theorem for reactively polynomial protocols. The theorem states that arbitrarily many instances of a secure protocol can be used in any larger protocol without sacrificing security. Our proof is technically different from and substantially more involved than proofs for previous protocol composition theorems (for previous definitions of polynomial runtime). We believe that it is precisely this additional proof complexity, which appears only once and for all in the proof of the composition theorem, that makes a useful definition as simple as ours possible.
Category / Keywords: foundations / Universal composability, polynomial runtime, multi-party protocols, protocol composition Date: received 12 Jan 2009 Contact author: unruh at mmci uni-saarland de Available format(s): PDF | BibTeX Citation Version: 20090113:193354 (All versions of this report) Discussion forum: Show discussion | Start new discussion