ETH Series in Information Security and Cryptography
edited by Ueli Maurer
Volume 6

Krzysztof Pietrzak
Indistinguishability and Composition
of Random Systems

1st edition/ 1. Auflage 2006, 172 pages/Seiten, 64,00. ISBN 3-86628-063-7

Many security proofs for cryptographic systems are achieved by showing that the system at hand is indistinguishable from some ideal and thus trivially secure system. For example an ideal block-cipher is a uniform random permutation and an ideal authentication scheme is a uniform random function.
In this thesis we develop and apply techniques to prove the indistinguishability of constructions, assuming some indistinguishability of the underlying components. Maurer's framework from Eurocrypt'02 is the starting point for this thesis.
For example we show that the sequential composition g(f(.)) of two non-adaptively secure (meaning indistinguishable from a random function) functions f(.) and g(.), is always adaptively secure in the information theoretic setting, but in general not in the computational setting (i.e. for pseudorandom systems).

Keywords: Cryptograhpy, Pseudorandomness, Quasirandomness, Indistinguishability, Random-systems, Luby-Rackoff cipher, Minicrypt, Key-agreement.

Bookorders at / Buchbestellungen in Ihrer Buchhandlung oder direkt:

Hartung-Gorre Verlag D-78465 Konstanz // Germany

Telefon: +49 (0) 7533 97227 // Telefax: +49 (0) 7533 97228


ETH Series in Information Security and Cryptography