Compactness of hashing modes and efficiency beyond Merkle tree

DOI10.1007/978-3-030-77886-6_4MaRDI QIDQ2056724zbMATH OpenOpenAlexFDO

Authors E. A. Andreeva, Rishiraj Bhattacharyya, Arnab Roy

Publication date 8 December 2021

Full work available at URL https://arxiv.org/abs/2104.15055

zbMATH Keywords

compactness efficiencyoptimally efficient cryptographically secure hash functions

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25) Cryptography (94A60)

Abstract: 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-epsilon}$-query collision resistance. Designing optimally efficient and secure hash functions for larger domains ($>2n$ bits) is still an open problem. In this work we propose the new extit{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 -Our first construction is an underline{A}ugmented underline{B}inary Tunderline{r}ee (ABR) mode. The design is a $(2^{ell}+2^{ell-1}-1)n$-to-$n$-bit hash function making a total of $(2^{ell}-1)$ calls to $2n$-to-$n$-bit compression functions for any $ellgeq2$. Our construction is optimally compact with asymptotically (optimal) $2^{n/2-epsilon}$-query collision resistance in the ideal model. For a tree of height $ell$, in comparison with Merkle tree, the $ABR$ mode processes additional $(2^{ell-1}-1)$ data blocks making the same number of internal compression function calls. -While the $ABR$ mode achieves collision resistance, it fails to achieve indifferentiability from a random oracle within $2^{n/3}$ queries. $AB{R}^{+}$ 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-epsilon}$ queries.

Recommendations

• Time-space tradeoffs and short collisions in Merkle-Damgård hash functions
• On time-space tradeoffs for bounded-length collisions in Merkle-Damgård hashing
• On time-space tradeoffs for bounded-length collisions in Merkle-Damgård hashing
• On the computation-storage trade-offs of hash chain traversal
• scientific article; zbMATH DE number 1722677
• scientific article; zbMATH DE number 1688373
• On the Circuit Complexity of Perfect Hashing
• Fast scalable construction of ([compressed] static | minimal perfect hash) functions
• Time-space lower bounds for finding collisions in Merkle-Damgård hash functions
• Generalized Merkle trees and their applications

Cites work

• A Simple and Unified Method of Proving Indistinguishability
• Beyond Uniformity: Better Security/Efficiency Tradeoffs for Compression Functions
• Building a Collision-Resistant Compression Function from Non-compressing Primitives
• Careful with composition: limitations of the indifferentiability framework
• CMSS – An Improved Merkle Signature Scheme
• Compactness of hashing modes and efficiency beyond Merkle tree
• Constructing Cryptographic Hash Functions from Fixed-Key Blockciphers
• Duplexing the sponge: Single-pass authenticated encryption and other applications
• Hash functions based on three permutations: a generic security analysis
• How to Build a Hash Function from Any Collision-Resistant Function
• How to Time-Stamp a Digital Document
• scientific article; zbMATH DE number 4195165 (Why is no real title available?)
• scientific article; zbMATH DE number 1942427 (Why is no real title available?)
• scientific article; zbMATH DE number 1942429 (Why is no real title available?)
• Keccak
• Merkle Signatures with Virtually Unlimited Signature Capacity
• On the Impossibility of Highly-Efficient Blockcipher-Based Hash Functions
• On the indifferentiability of the Grøstl hash function
• On the Indifferentiability of the Sponge Construction
• Quadratic span programs and succinct NIZKs without PCPs
• Scalable zero knowledge via cycles of elliptic curves
• Security reductions of the second round SHA-3 candidates
• Security/Efficiency Tradeoffs for Permutation-Based Hashing
• Stam's collision resistance conjecture
• Stam's conjecture and threshold phenomena in collision resistance
• The “Coefficients H” Technique
• Theory of Cryptography
• Tight security bounds for key-alternating ciphers

Cited in

(12)

• Compactness of hashing modes and efficiency beyond Merkle tree
• Collision-resistant and pseudorandom function based on Merkle-Damgård hash function
• On the memory-tightness of hashed ElGamal
• Speeding up the wide-pipe: secure and fast hashing
• Merkle Tree Traversal Revisited
• Collapseability of tree hashes
• Sakura: a flexible coding for tree hashing
• Merkle tree ladder mode: reducing the size impact of NIST PQC signature algorithms in practice
• T5: Hashing five inputs with three compression calls
• Block-cipher-based tree hashing
• Generalized indifferentiable sponge and its application to Polygon Miden VM
• Lower bound on number of compression calls of a collision-resistance preserving hash

This page was built for publication: Compactness of hashing modes and efficiency beyond Merkle tree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2056724)