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).
Category / Keywords: foundations / Hash functions, Random oracle, Indifferentiability, Multi-stage Date: received 15 May 2013, last revised 16 May 2013 Contact author: arno mittelbach at cased de Available formats: PDF | BibTeX Citation Version: 20130523:161954 (All versions of this report) Discussion forum: Show discussion | Start new discussion