2022/01/26 by Bertoni, Guido, Daemen, Joan, Peeters, Michaël +1
#Indifferentiability #Tree Hashing
paper · doi:10.4230/dagsemproc.09031.15
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 q2/2n 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.