When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-19463
Go to the corresponding Portal

Bertoni, Guido ; Daemen, Joan ; Peeters, MichaŽl ; Van Assche, Gilles

Sufficient conditions for sound tree hashing modes

09031.DaemenJoan.ExtAbstract.1946.pdf (0.1 MB)


We consider the general case of tree hashing modes that make use of an underlying compression function. We consider such a tree hashing mode sound if differentiating it from a random oracle, assuming the underlying compression function is a random oracle can be proven to be hard. We demonstrate two properties that such a tree hashing mode must have for such a proof to exist. For each of the two properties we show that several solutions exist to realize them. For some given solutions we demonstrate that a simple proof of indifferentiability exists and obtain an upper bound on the differentiability probability of $q^2/2^n$ with $q$ the number of queries to the underlying compression function and $n$ its output length. Finally we give two examples of hashing modes for which this proof applies: KeccakTree and Prefix-free Merkle-Damgard.

BibTeX - Entry

  author =	{Guido Bertoni and Joan Daemen and Micha{\"e}l Peeters and Gilles Van Assche},
  title =	{Sufficient conditions for sound tree hashing modes},
  booktitle =	{Symmetric Cryptography },
  year =	{2009},
  editor =	{Helena Handschuh and Stefan Lucks and Bart Preneel and Phillip Rogaway},
  number =	{09031},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{},
  annote =	{Keywords: Tree Hashing, Indifferentiability}

Keywords: Tree Hashing, Indifferentiability
Seminar: 09031 - Symmetric Cryptography
Issue Date: 2009
Date of publication: 30.03.2009

DROPS-Home | Fulltext Search | Imprint Published by LZI