Compactness of hashing modes and efficiency beyond Merkle tree

Elena Andreeva*, Rishiraj Bhattacharyya, Arnab Roy

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Downloads (Pure)


We revisit the classical problem of designing optimally efficient cryptographically secure hash functions. Hash functions are traditionally designed via applying modes of operation on primitives with smaller domains. The results of Shrimpton and Stam (ICALP 2008), Rogaway and Steinberger (CRYPTO 2008), and Mennink and Preneel (CRYPTO 2012) show how to achieve optimally efficient designs of 2n-to-n-bit compression functions from non-compressing primitives with asymptotically optimal 2 n/2-ϵ -query collision resistance. Designing optimally efficient and secure hash functions for larger domains (> 2 n bits) is still an open problem. To enable efficiency analysis and comparison across hash functions built from primitives of different domain sizes, in this work we propose the new compactness efficiency notion. It allows us to focus on asymptotically optimally collision resistant hash function and normalize their parameters based on Stam’s bound from CRYPTO 2008 to obtain maximal efficiency. We then present two tree-based modes of operation as a design principle for compact, large domain, fixed-input-length hash functions. 1.Our first construction is an Augmented Binary Tree (ABR) mode. The design is a (2 + 2 -1- 1 ) n -to-n-bit hash function making a total of (2 - 1 ) calls to 2n-to-n-bit compression functions for any ℓ≥ 2. Our construction is optimally compact with asymptotically (optimal) 2 n/2-ϵ -query collision resistance in the ideal model. For a tree of height ℓ, in comparison with Merkle tree, the ABR mode processes additional (2 -1- 1 ) data blocks making the same number of internal compression function calls.2.With our second design we focus our attention on the indifferentiability security notion. While the ABR mode achieves collision resistance, it fails to achieve indifferentiability from a random oracle within 2 n/3 queries. ABR+ compresses only 1 less data block than ABR with the same number of compression calls and achieves in addition indifferentiability up to 2 n/2-ϵ queries. Both of our designs are closely related to the ubiquitous Merkle Trees and have the potential for real-world applicability where the speed of hashing is of primary interest.

Original languageEnglish
Title of host publicationAdvances in Cryptology – EUROCRYPT 2021
Subtitle of host publication40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, October 17–21, 2021, Proceedings, Part II
EditorsAnne Canteaut, François-Xavier Standaert
Number of pages32
ISBN (Electronic)9783030778866
ISBN (Print)9783030778859
Publication statusPublished - 16 Jun 2021
Event40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2021 - Zagreb, Croatia
Duration: 17 Oct 202121 Oct 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12697 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2021

Bibliographical note

Funding Information:
Acknowledgements. We thank Martijn Stam for reading an earlier version of the draft and providing valuable comments. We would like to also thank Markulf Kohlweiss for discussion on the zksnarks and other applications of this work. We sincerely thank the reviewers of this and the earlier version of this paper for their insightful comments. Rishiraj is supported by SERB ECR/2017/001974.

Publisher Copyright:
© 2021, International Association for Cryptologic Research.

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Compactness of hashing modes and efficiency beyond Merkle tree'. Together they form a unique fingerprint.

Cite this