ETH Zürich » Computer Science » Theory » Cryptography

Abstract Cryptography

The goal of this research initiative is to treat cryptographic concepts and results at the highest possible abstract level, thereby achieving generality and simplicity at the same time. Many results in cryptography, for instance in the area of indistinguishability proofs, can be simplified and generalized substantially when considered at an abstract level.


Research Highlights

  • Indistinguishability amplification. [MPR07] presents a new generic approach to proving upper bounds on the information-theoretic distinguishing advantage (from an ideal system) for a combined system, based on upper bounds for the component systems. For a general type of combination operation of systems, including the XOR of functions or the cascade of permutations, two amplification theorems are proved. The first is a product theorem, in the spirit of XOR-lemmas: The distinguishing advantage of the combination of two systems is at most twice the product of the individual distinguishing advantages. This bound is optimal. The second theorem states that the combination of systems is secure against some strong class of distinguishers, assuming only that the components are secure against some weaker class of distinguishers.
  • Indifferentiability theory. In [MRH04] a generalized notion of indistinguishability was introduced which can be applied to primitives that are publicly accessible, like a hash function. The theory of indifferentiability has many applications: it allows to prove the impossibility of realizing a random oracle as well as to prove the security and soundness of hash function constructions. It is also the basis for providing domain extension of public random functions, see [MT07].
  • Random systems and indistinguishability theory. Many aspects of cryptographic security proofs can be seen as the proof that a certain system (e.g. a block cipher) is indistinguishable from an ideal system (e.g. a random permutation), for different types of distinguishers. [Mau02] introduces the abstract concept of a random system and develops a theory of indistinguishability of random systems. Many complex security proofs (Luby-Rackoff, CBC-MAC, switching lemma, etc.) in the literature are instantiations of a general theorem on random systems.

Publications Concerning This Topic

Ueli Maurer and Stefano Tessaro
Domain Extension of Public Random Functions: Beyond the Birthday Barrier
Advances in Cryptology — CRYPTO 2007, Lecture Notes in Computer Science, Springer-Verlag, vol. 4622, pp. 187–204, Aug 2007, Full version available from http://eprint.iacr.org/2007/229.
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Ueli Maurer, Krzysztof Pietrzak, and Renato Renner
Indistinguishability Amplification
Advances in Cryptology — CRYPTO 2007, Lecture Notes in Computer Science, Springer-Verlag, vol. 4622, pp. 130–149, Aug 2007.
Available files: [ PDF ] [ Abstract ] [ BibTeX ]
Ueli Maurer, Renato Renner, and Clemens Holenstein
Indifferentiability, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology
Theory of Cryptography Conference — TCC 2004, Lecture Notes in Computer Science, Springer-Verlag, vol. 2951, pp. 21–39, Feb 2004.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]
Ueli Maurer
Indistinguishability of Random Systems
Advances in Cryptology — EUROCRYPT 2002, Lecture Notes in Computer Science, Springer-Verlag, vol. 2332, pp. 110–132, May 2002.
Available files: [ PS ] [ PDF ] [ Abstract ] [ BibTeX ]

© IACR | Springer | ACM | IEEE


Main Research Page