IACR News item: 01 November 2012
Grégory Demay, Peter Gazi, Martin Hirt, Ueli Maurer
ePrint ReportIn this paper we argue that one general reason for such a failure is the inflexibility of the indifferentiability notion with respect to more complex restrictions on resources (such as memory, randomness) available to the attacker: Typically, the distinguisher and the simulator in an indifferentiability statement are only required to be PPT algorithms, implicitly posing a polynomial restriction also on the resources available to them. We argue that this is not sufficient in certain scenarios and explain why this is the problem underlying the security breakdown described in [RSS11]. We present a systematic treatment of such settings by proposing a more fine-grained notion of memory-aware reducibility that is necessary in contexts when memory is the resource that requires a more detailed quantification.
We employ this new formalism to prove a lower bound on the memory required by any simulator in a domain extension construction of a public random function. Our results imply that if we restrict to simulators without memory, even domain extension by a single bit becomes impossible. On the other hand, for the infinite extension from an ideal compression function to a random oracle, a memory roughly linear in the total sum of the lengths of all queries is required. This solves an open problem given in [RSS11].
Finally, it follows from our results that for any multi-party setting where one cannot assume the existence of a central adversary and hence it requires to be modeled using an independent local simulator for each party, it is impossible to securely construct a public random oracle from a public ideal compression function.
Additional news items may be found on the IACR news page.