Bertoni, Guido ;
Daemen, Joan ;
Peeters, Michaël ;
Van Assche, Gilles
Sufficient conditions for sound tree hashing modes
Abstract
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 Prefixfree MerkleDamgard.
BibTeX  Entry
@InProceedings{bertoni_et_al:DSP:2009:1946,
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 = {18624405},
publisher = {Schloss Dagstuhl  LeibnizZentrum fuer Informatik, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2009/1946},
annote = {Keywords: Tree Hashing, Indifferentiability}
}
2009
Keywords: 

Tree Hashing, Indifferentiability 
Seminar: 

09031  Symmetric Cryptography

Related Scholarly Article: 


Issue date: 

2009 
Date of publication: 

2009 