Portal de Periódicos da CAPES

Fractal Merkle Tree Representation and Traversal

2003; Springer Science+Business Media; Linguagem: Inglês

10.1007/3-540-36563-x_21

1611-3349

Markus Jakobsson, Tom Leighton, Silvio Micali, Michael Szydlo,

Advanced Steganography and Watermarking Techniques

We introduce a technique for traversal of Merkle trees, and propose an efficient algorithm that generates a sequence of leaves along with their associated authentication paths. For one choice of parameters, and a total of N leaves, our technique requires a worst-case computational effort of 2 logN/loglog N hash function evaluations per output, and a total storage capacity of less than 1.5 log2 N/loglogN hash values. This is a simultaneous improvement both in space and time complexity over any previously published algorithm.