You are looking at a specific version 20130523:161954 of this paper. See the latest version.

Paper 2013/286

Salvaging Indifferentiability in a Multi-stage Setting

Arno Mittelbach

Abstract

Ristenpart, Shacham and Shrimpton (Eurocrypt 2011) recently presented schemes which are provably secure in the random-oracle model (ROM), but 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).

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
Hash functionsRandom oracleIndifferentiabilityMulti-stage
Contact author(s)
arno mittelbach @ cased de
History
2014-05-08: last of 2 revisions
2013-05-23: received
See all versions
Short URL
https://ia.cr/2013/286
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.