IACR News item: 27 May 2013
Arno Mittelbach
ePrint Reportbut easily broken if the random oracle is replaced by typical indifferentiable hash constructions such as chop-MD or prefix-free-MD.
They found that the indifferentiability framework, due to Maurer, Renner and Holenstein (TCC 2004), does not
necessarily allow composition in multi-stage settings, that is, settings consisting of multiple disjoint adversarial stages. On the positive
side, they prove that the non-adaptive chosen distribution attack (CDA) game of Bellare et al.~(Asiacrypt 2009), a multi-stage game capturing the security of deterministic encryption schemes,
remains secure if the random oracle is implemented by an NMAC-like hash function.
In this paper we introduce a framework to work with the indifferentiability notion in multi-stage scenarios. For this we provide
a model for iterative hash functions which is general enough to cover not only NMAC-like functions, but also functions such as chop-MD
or even hash trees. We go on to define a property on multi-stage games called \\emph{unsplittability} which intuitively captures that
adversaries cannot split the computation of a single hash value over several stages. We present a composition theorem for
unsplittable multi-stage games which generalizes the single-stage composition theorem for indifferentiable hash functions. We then show that
the CDA game (adaptive or non-adaptive) is unsplittable for \\emph{any} iterative hash function (thereby extending the preliminary results
by Ristenpart et al.). Finally, we prove that the \\emph{proof-of-storage} game presented by Ristenpart et al.~as a counterexample to
the general applicability of the indifferentiability framework is unsplittable for any multi-round iterative hash function, such as
Liskov\'s Zipper Hash (SAC~2006).
Additional news items may be found on the IACR news page.