1 Search Results for "Mouha, Nicky"

Document

DOI: 10.4230/LIPIcs.ITC.2021.24

T₅: Hashing Five Inputs with Three Compression Calls

Authors: Yevgeniy Dodis, Dmitry Khovratovich, Nicky Mouha, and Mridul Nandi

Published in: LIPIcs, Volume 199, 2nd Conference on Information-Theoretic Cryptography (ITC 2021)

Abstract

Given 2n-to-n compression functions h₁,h₂,h₃, we build a new 5n-to-n compression function T₅, using only 3 compression calls: T₅(m₁, m₂, m₃, m₄, m₅) : = h₃(h₁(m₁, m₂)⊕ m₅ , h₂(m₃, m₄)⊕ m₅) ⊕ m₅ We prove that this construction matches Stam’s bound, by providing Õ(q²/2ⁿ) collision security and O(q³/2^{2n}+ nq/2ⁿ) 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 Merkle-Damgå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 MD-hashing, 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(t-1) compression function calls and depth 0.86 log₂ 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.29log₂ t vs log₂ t), but the verification time is now 14% faster (0.86log₂ t vs log₂ t). However, birthday security is only shown under a plausible conjecture related to the 3-XOR 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.

Cite as

Yevgeniy Dodis, Dmitry Khovratovich, Nicky Mouha, and Mridul Nandi. T₅: Hashing Five Inputs with Three Compression Calls. In 2nd Conference on Information-Theoretic Cryptography (ITC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 199, pp. 24:1-24:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{dodis_et_al:LIPIcs.ITC.2021.24,
  author =	{Dodis, Yevgeniy and Khovratovich, Dmitry and Mouha, Nicky and Nandi, Mridul},
  title =	{{T₅: Hashing Five Inputs with Three Compression Calls}},
  booktitle =	{2nd Conference on Information-Theoretic Cryptography (ITC 2021)},
  pages =	{24:1--24:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-197-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{199},
  editor =	{Tessaro, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2021.24},
  URN =		{urn:nbn:de:0030-drops-143430},
  doi =		{10.4230/LIPIcs.ITC.2021.24},
  annote =	{Keywords: hash functions, Merkle trees, Merkle-Damg\r{a}rd, collision resistance}
}

Refine by Author
1 Dodis, Yevgeniy
1 Khovratovich, Dmitry
1 Mouha, Nicky
1 Nandi, Mridul

Refine by Classification
1 Security and privacy → Cryptography

Refine by Keyword
1 Merkle trees
1 Merkle-Damgård
1 collision resistance
1 hash functions

Refine by Type
1 document

Refine by Publication Year
1 2021

1 Search Results for "Mouha, Nicky"

T₅: Hashing Five Inputs with Three Compression Calls

Abstract

Cite as

Thanks for your feedback!

Could not send message