Paper 2021/373
T5: Hashing Five Inputs with Three Compression Calls
Yevgeniy Dodis, Dmitry Khovratovich, Nicky Mouha, and Mridul Nandi
Abstract
Given $2n$to$n$ compression functions $h_1,h_2,h_3$, we build a new $5n$to$n$ compression function $\mathrm{T}_5$, using only $3$ compression calls: $\mathrm{T}_5(m_1, m_2, m_3, m_4, m_5) := h_3( h_1(m_1, m_2)\oplus m_5, h_2(m_3, m_4)\oplus m_5) \oplus m_5$. We prove that this construction matches Stam's bound, by providing $\tilde{O}(q^2/2^n)$ collision security and $O(q^3/2^{2n}+ nq/2^n)$ preimage security (the latter term dominates in the region of interest, when $q<2^{n/2}$). In particular, it provides birthday security for hashing $5$ inputs using three $2n$to$n$ compression calls, instead of only $4$ inputs in prior constructions. Thus, we get a sequential variant of the MerkleDamgård (MD) hashing, where $t$ message blocks are hashed using only $3t/4$ calls to the $2n$to$n$ compression functions; a $25\%$ saving over traditional hash function constructions. This time reduces to $t/4$ (resp. $t/2$) sequential calls using $3$ (resp. $2$) parallel execution units; saving a factor of $4$ (resp. $2$) over the traditional MDhashing, where parallelism does not help to process one message. We also get a novel variant of a Merkle tree, where $t$ message blocks can be processed using $0.75(t1)$ compression function calls and depth $0.86 \log_2 t$, thereby saving $25\%$ in the number of calls and $14\%$ in the update time over Merkle trees. We provide two modes for a local opening of a particular message block: conservative and aggressive. The former retains the birthday security, but provides longer proofs and local verification time than the traditional Merkle tree. For the aggressive variant, we reduce the proof length to a $29\%$ overhead compared to Merkle trees ($1.29\log_2 t$ vs $\log_2 t$), but the verification time is now $14\%$ faster ($0.86\log_2 t$ vs $\log_2 t$). However, birthday security is only shown under a plausible conjecture related to the 3XOR problem, and only for the (common, but not universal) setting where the root of the Merkle tree is known to correspond to a valid $t$block message.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published elsewhere. MAJOR revision.ITC 2021
 DOI
 10.4230/LIPIcs.ITC.2021.25
 Keywords
 hash functionsMerkle treesMerkleDamgardcollisionresistancecompression function
 Contact author(s)

dodis @ cs nyu edu
khovratovich @ gmail com
nicky @ mouha be
mridul nandi @ gmail com  History
 20210514: revised
 20210322: received
 See all versions
 Short URL
 https://ia.cr/2021/373
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/373, author = {Yevgeniy Dodis and Dmitry Khovratovich and Nicky Mouha and Mridul Nandi}, title = {T5: Hashing Five Inputs with Three Compression Calls}, howpublished = {Cryptology ePrint Archive, Paper 2021/373}, year = {2021}, doi = {10.4230/LIPIcs.ITC.2021.25}, note = {\url{https://eprint.iacr.org/2021/373}}, url = {https://eprint.iacr.org/2021/373} }