Maurer, Renner, Holenstein: “Indifferentiablility, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology”

06.03.2019, 10:00

06.03.2019 10:00-11:00

Speaker: Jacqueline Brendel, TU Darmstadt | Location: Mornewegstraße 32 (S4|14), Room 5.3.01, Darmstadt

Organizer: Christian Janson, Cryptoplexity Group

This talk is the fifth one in the seminar series „Reading the Crypto Classics“ for the winter term 2018/2019. The idea of this seminar is to jointly read classical milestone papers in the area of cryptography, to discuss their impact and understand their relevance for current research areas. The seminar is running as an Oberseminar, but at the same time meant to be a joint reading group seminar of the CROSSING Special Interest Group on Advanced Cryptography with all interested CROSSING members being invited to participate.

This issue will cover the paper

Maurer, Renner, Holenstein: “Indifferentiablility, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology” (TCC 2004), DOI: 10.1007/978-3-540-24638-1_2 with the following abstract:

„The goals of this paper are two-fold. First we introduce and motivate a generalization of the fundamental concept of the indistinguishability of two systems, called indifferentiability. This immediately leads to a generalization of the related notion of reducibility of one system to another. In contrast to the conventional notion of indistinguishability, indifferentiability is applicable in settings where a possible adversary is assumed to have access to additional information about the internal state of the involved systems, for instance the public parameter selecting a member from a family of hash functions.

Second, we state an easily verifiable criterion for a system U not to be reducible (according to our generalized definition) to another system V and, as an application, prove that a random oracle is not reducible to a weaker primitive, called asynchronous beacon, and also that an asynchronous beacon is not reducible to a finite-length random string. Each of these irreducibility results alone implies the main theorem of Canetti, Goldreich, and Halevi stating that there exist cryptosystems that are secure in the random oracle model but for which replacing the random oracle by any implementation leads to an insecure cryptosystem.“

Short bio
Jacqueline is a fourth-year Ph.D. candidate in Prof. Marc Fischlin's group „Cryptography and Complexity Theory“. Before recently joining CROSSING as part of project S4, Jacqueline has been involved in the Research Training Group „Privacy and Trust for Mobile Users“. Her research interests are in applied cryptography, with a particular focus on building future-proof key exchange protocols in a provably secure manner.