Protokollkomposition und Komplexität

Dominique Unruh.
Ph.D. thesis, Universität Karlsruhe (TH), Logos Berlin, 2007. In German.


In the setting of Reactive Simulatability/UC there are two different notions of security differing in the order of quantifiers. In the case of universal security/UC, the environment is chosen depending on the simulator, while in the case of general security/specialised-simulator UC the simulator may depend on the environment. It was a longstanding open question whether these two notions are equivalent.

Furthermore, the notion of (polynomially-bounded) general composability has been introduced. It captures the minimal security notion that allow for a certain general kind of secure composition. Although it was known that universal security implies general composability, the relation to the other notions was open.

We analyse all open relations between these security notions in the case of computational, statistical and perfect security. We show that for computational security, the three notions are different, that is universal security strictly implies general composability which in turn strictly implies general security (given a natural complexity assumption). For statistical security universal security and general composability coincide and strictly imply general security (although when allowing only protocols running in polynomial time, all three notions). And for perfect security all three notions coincide. This gives an answer to the open problems mentioned above.

For showing these relations, we introduced several new techniques. First, the complexity assumption of so-called time-lock puzzles is investigated and shown to be a very effective tool for constructing separating examples between security notions. Further the usefulness of game-theoretic techniques for showing equivalences between different notions of statistical security is demonstrated.

The thesis is written in German. Wide parts of this thesis are covered by the English papers Comparing Two Notions of Simulatability by Hofheinz and Unruh, Simulatable Security and Polynomially Bounded Concurrent Composition by Hofheinz and Unruh and Relations among Statistical Security Notions - or - Why Exponential Adversaries are Unlimited by Unruh.

Files available online

This publication is accompanied by links to downloadable versions of this publication. These documents do not necessarily correspond exactly to the cited version. Instead, in most cases full, updated or preliminary versions are provided. For access to the official version, follow the "Official version" link to the publishers site.

Slides used in my talks are available upon personal request, as long as you agree not to disseminate them to a wider audience or make them available online. If in doubt, please ask.