Protokollkomposition und Komplexität (2007)
Dominique Unruh
[ eprint | official ]
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 [CITE hofheinz05comparing], [CITE hofheinz06simulatable] and [CITE unruh05relations].