T₅: Hashing Five Inputs with Three Compression Calls

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



PDF
Thumbnail PDF

File

LIPIcs.ITC.2021.24.pdf
  • Filesize: 1 MB
  • 23 pages

Document Identifiers

Author Details

Yevgeniy Dodis
  • New York University, NY, USA
Dmitry Khovratovich
  • Ethereum Foundation, Luxembourg, Luxembourg
  • Dusk Network, Luxembourg, Luxembourg
Nicky Mouha
  • Strativia, Largo, MD, USA
Mridul Nandi
  • Indian Statistical Institute, Kolkata, India

Acknowledgements

Thanks to the organizers and participants of Dagstuhl Seminar 18021 "Symmetric Cryptography," held from January 7-12, 2018 at Schloss Dagstuhl - Leibniz Center for Informatics. The T₅ construction was first presented there by one of the authors of this paper, and the fruitful discussions there provided an initial starting point for this paper.

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.ITC.2021.24

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 Õ(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.

Subject Classification

ACM Subject Classification
  • Security and privacy → Cryptography
Keywords
  • hash functions
  • Merkle trees
  • Merkle-Damgård
  • collision resistance

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In STOC, pages 1-10. ACM, 1988. Google Scholar
  2. Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. Fast Reed-Solomon interactive oracle proofs of proximity. In ICALP, volume 107 of LIPIcs, pages 14:1-14:17. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  3. Eli Ben-Sasson, Alessandro Chiesa, and Nicholas Spooner. Interactive oracle proofs. In TCC (B2), volume 9986 of Lecture Notes in Computer Science, pages 31-60, 2016. Google Scholar
  4. Piotr Berman, Marek Karpinski, and Yakov Nekrich. Optimal trade-off for merkle tree traversal. Theor. Comput. Sci., 372(1):26-36, 2007. Google Scholar
  5. Daniel J Bernstein, Daira Hopwood, Andreas Hülsing, Tanja Lange, Ruben Niederhagen, Louiza Papachristodoulou, Michael Schneider, Peter Schwabe, and Zooko Wilcox-O’Hearn. SPHINCS: practical stateless hash-based signatures. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 368-397. Springer, 2015. Google Scholar
  6. John Black, Martin Cochran, and Thomas Shrimpton. On the impossibility of highly-efficient blockcipher-based hash functions. In EUROCRYPT, volume 3494 of Lecture Notes in Computer Science, pages 526-541. Springer, 2005. Google Scholar
  7. John Black, Martin Cochran, and Thomas Shrimpton. On the impossibility of highly-efficient blockcipher-based hash functions. J. Cryptol., 22(3):311-329, 2009. Google Scholar
  8. Charles Bouillaguet, Claire Delaplace, and Pierre-Alain Fouque. Revisiting and improving algorithms for the 3xor problem. IACR Trans. Symmetric Cryptol., 2018(1):254-276, 2018. Google Scholar
  9. Larry Carter and Mark N. Wegman. Universal classes of hash functions. J. Comput. Syst. Sci., 18(2):143-154, 1979. Google Scholar
  10. Ivan Damgård. A design principle for hash functions. In CRYPTO, volume 435 of Lecture Notes in Computer Science, pages 416-427. Springer, 1989. Google Scholar
  11. Yevgeniy Dodis, Dmitry Khovratovich, Nicky Mouha, and Mridul Nandi. T5: hashing five inputs with three compression calls. IACR Cryptology ePrint Arch., 2021:373, 2021. Full version of this paper. Google Scholar
  12. Oded Goldreich, Silvio Micali, and Avi Wigderson. How to play any mental game or A completeness theorem for protocols with honest majority. In STOC, pages 218-229. ACM, 1987. Google Scholar
  13. Iftach Haitner, Yuval Ishai, Eran Omri, and Ronen Shaltiel. Parallel hashing via list recoverability. In CRYPTO, volume 9216 of Lecture Notes in Computer Science, pages 173-190. Springer, 2015. Google Scholar
  14. Daira Hopwood, Sean Bowe, Taylor Hornby, and Nathan Wilcox. Zcash protocol specification: Version 2019.0-beta-37 [overwinter+sapling]. Technical report, Zerocoin Electric Coin Company, 2019. available at URL: https://github.com/zcash/zips/blob/master/protocol/protocol.pdf.
  15. Markus Jakobsson, Frank Thomson Leighton, Silvio Micali, and Michael Szydlo. Fractal merkle tree representation and traversal. In CT-RSA, volume 2612 of Lecture Notes in Computer Science, pages 314-326. Springer, 2003. Google Scholar
  16. Lars R. Knudsen and Bart Preneel. Construction of secure and fast hash functions using nonbinary error-correcting codes. IEEE Trans. Inf. Theory, 48(9):2524-2539, 2002. Google Scholar
  17. Ian McQuoid, Trevor Swope, and Mike Rosulek. Characterizing collision and second-preimage resistance in linicrypt. In Dennis Hofheinz and Alon Rosen, editors, TCC, volume 11891 of Lecture Notes in Computer Science, pages 451-470. Springer, 2019. Google Scholar
  18. Bart Mennink and Bart Preneel. Hash functions based on three permutations: A generic security analysis. In CRYPTO, volume 7417 of Lecture Notes in Computer Science, pages 330-347. Springer, 2012. Google Scholar
  19. Bart Mennink and Bart Preneel. Efficient parallelizable hashing using small non-compressing primitives. Int. J. Inf. Sec., 15(3):285-300, 2016. Google Scholar
  20. Ralph C. Merkle. Protocols for public key cryptosystems. In IEEE Symposium on Security and Privacy, pages 122-134. IEEE Computer Society, 1980. Google Scholar
  21. Ralph C. Merkle. One way hash functions and DES. In CRYPTO, volume 435 of Lecture Notes in Computer Science, pages 428-446. Springer, 1989. Google Scholar
  22. Mridul Nandi, Wonil Lee, Kouichi Sakurai, and Sangjin Lee. Security analysis of a 2/3-rate double length compression function in the black-box model. In FSE, volume 3557 of Lecture Notes in Computer Science, pages 243-254. Springer, 2005. Google Scholar
  23. Ivica Nikolic and Yu Sasaki. Refinements of the k-tree algorithm for the generalized birthday problem. In ASIACRYPT, volume 9453 of Lecture Notes in Computer Science, pages 683-703. Springer, 2015. Google Scholar
  24. Mihai Patrascu and Mikkel Thorup. The power of simple tabulation hashing. J. ACM, 59(3):14:1-14:50, 2012. Google Scholar
  25. Alexey Pertsev, Roman Semenov, and Roman Storm. Tornado cash privacy solution version 1.4, 2019. URL: https://tornado.cash/Tornado.cash_whitepaper_v1.4.pdf.
  26. Thomas Peyrin, Henri Gilbert, Frédéric Muller, and Matthew J. B. Robshaw. Combining compression functions and block cipher-based hash functions. In ASIACRYPT, volume 4284, pages 315-331. Springer, 2006. Google Scholar
  27. Phillip Rogaway and John P. Steinberger. Security/efficiency tradeoffs for permutation-based hashing. In EUROCRYPT, volume 4965 of Lecture Notes in Computer Science, pages 220-236. Springer, 2008. Google Scholar
  28. Yannick Seurin and Thomas Peyrin. Security analysis of constructions combining FIL random oracles. In FSE, volume 4593, pages 119-136. Springer, 2007. Google Scholar
  29. Martijn Stam. Beyond uniformity: Better security/efficiency tradeoffs for compression functions. In CRYPTO, volume 5157 of Lecture Notes in Computer Science, pages 397-412. Springer, 2008. Google Scholar
  30. John P. Steinberger. Stam’s collision resistance conjecture. In EUROCRYPT, volume 6110 of Lecture Notes in Computer Science, pages 597-615. Springer, 2010. Google Scholar
  31. John P. Steinberger, Xiaoming Sun, and Zhe Yang. Stam’s conjecture and threshold phenomena in collision resistance. In CRYPTO, volume 7417 of Lecture Notes in Computer Science, pages 384-405. Springer, 2012. Google Scholar
  32. Michael Szydlo. Merkle tree traversal in log space and time. In EUROCRYPT, volume 3027 of Lecture Notes in Computer Science, pages 541-554. Springer, 2004. Google Scholar
  33. David A. Wagner. A generalized birthday problem. In CRYPTO, volume 2442 of Lecture Notes in Computer Science, pages 288-303. Springer, 2002. Google Scholar
  34. Riad S. Wahby, Ioanna Tzialla, Abhi Shelat, Justin Thaler, and Michael Walfish. Doubly-efficient zkSNARKs without trusted setup. In IEEE Symposium on Security and Privacy, pages 926-943. IEEE Computer Society, 2018. Google Scholar
  35. Tiancheng Xie, Jiaheng Zhang, Yupeng Zhang, Charalampos Papamanthou, and Dawn Song. Libra: Succinct zero-knowledge proofs with optimal prover computation. In CRYPTO, volume 11694 of Lecture Notes in Computer Science, pages 733-764. Springer, 2019. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail