When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.09031.15
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.08 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 =	{Bertoni, Guido and Daemen, Joan and Peeters, Micha\"{e}l and Van Assche, Gilles},
  title =	{{Sufficient conditions for sound tree hashing modes}},
  booktitle =	{Symmetric Cryptography},
  pages =	{1--1},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9031},
  editor =	{Helena Handschuh and Stefan Lucks and Bart Preneel and Phillip Rogaway},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-19463},
  doi =		{10.4230/DagSemProc.09031.15},
  annote =	{Keywords: Tree Hashing, Indifferentiability}

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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI