Paper 2009/210
Sufficient conditions for sound tree and sequential hashing modes
Guido Bertoni, Joan Daemen, Michael Peeters, and Gilles Van Assche
Abstract
Hash functions are usually composed of a mode of operation on top of a concrete primitive with fixed input-length and fixed output-length, such as a block cipher or a permutation. In practice, the mode is often sequential, although parallel (or tree) hashing modes are also possible. The former requires less memory, while the latter has several advantages such as its inherent parallelism and a lower cost of hash value re-computation when only a small part of the input changes. In this paper, we consider the general case of (tree or sequential) hashing modes that make use of an underlying hash function, which may in turn be sequential. We formulate a set of three simple conditions for such a (tree or sequential) hashing mode to be sound. By sound, we mean that the advantage in differentiating a hash function obtained by applying a tree hashing mode to an ideal underlying hash function from an ideal monolithic hash function is upper bounded by
Note: Changes detailed in Appendix A.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published elsewhere. Minor revision. International Journal of Information Security
- DOI
- 10.1007/s10207-013-0220-y
- Keywords
- tree hashingindifferentiability
- Contact author(s)
- keccak @ noekeon org
- History
- 2014-01-28: last of 3 revisions
- 2009-05-26: received
- See all versions
- Short URL
- https://ia.cr/2009/210
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2009/210, author = {Guido Bertoni and Joan Daemen and Michael Peeters and Gilles Van Assche}, title = {Sufficient conditions for sound tree and sequential hashing modes}, howpublished = {Cryptology {ePrint} Archive, Paper 2009/210}, year = {2009}, doi = {10.1007/s10207-013-0220-y}, url = {https://eprint.iacr.org/2009/210} }