Paper 2009/023
Polynomial Runtime and Composability
Dennis Hofheinz, Dominique Unruh, and Jörn MüllerQuade
Abstract
To prove security of a multiparty cryptographic protocol, one often reduces attacks on the protocol to attacks on a suitable computational problem. Thus, if the computational problem is hard, then the protocol is secure. But to allow for a security reduction, the protocol itself and the attack on the protocol must be efficient, i.e., polynomialtime. Of course, the obvious way to enforce an overall polynomial runtime of the protocol is to require each individual protocol machine and adversarial entity to be polynomialtime. However, as the specific case of zeroknowledge protocols demonstrates, an a priori polynomialtime bound on all entities may not be an optimal choice because the running time of some machines needs to depend on that of others. As we want to be able to model arbitrary protocol tasks, we work in the Universal Composability framework (UC). This framework additionally provides strong composability guarantees. We will point out that in the UC setting, finding a useful notion of polynomialtime for the analysis of general protocols is a highly nontrivial task. Our goal in this work is to find a good and useful definition of polynomialtime for multiparty 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 polynomialtime. * Soundness: All "intuitively feasible" attacks (i.e., adversaries) should be considered polynomialtime. * Completeness: Only "intuitively feasible" attacks should be considered polynomialtime. 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.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published elsewhere. Unknown where it was published
 Keywords
 Universal composabilitypolynomial runtimemultiparty protocolsprotocol composition
 Contact author(s)
 unruh @ mmci unisaarland de
 History
 20090113: received
 Short URL
 https://ia.cr/2009/023
 License

CC BY
BibTeX
@misc{cryptoeprint:2009/023, author = {Dennis Hofheinz and Dominique Unruh and Jörn MüllerQuade}, title = {Polynomial Runtime and Composability}, howpublished = {Cryptology ePrint Archive, Paper 2009/023}, year = {2009}, note = {\url{https://eprint.iacr.org/2009/023}}, url = {https://eprint.iacr.org/2009/023} }