Lower Bound on Number of Compression Calls of a Collision-Resistance Preserving Hash
Authors
Debasmita Chakraborty, Mridul Nandi
Debasmita Chakraborty
Indian Statistical Institute, Kolkata, India
debasmitachakraborty1 at gmail dot com
debasmitachakraborty1 at gmail dot com
Mridul Nandi
Indian Statistical Institute, Kolkata, India
mridul dot nandi at gmail dot com
mridul dot nandi at gmail dot com
Abstract
The collision-resistant hash function is an early cryptographic primitive that finds extensive use in various applications. Remarkably, the Merkle-Damgård and Merkle tree hash structures possess the collision-resistance preserving property, meaning the hash function remains collision-resistant when the underlying compression function is collision-resistant. This raises the intriguing question of whether reducing the number of underlying compression function calls with the collision-resistance preserving property is possible. In pursuit of addressing these inquiries, we prove that for an ${\ell}n$-to-$sn$-bit collision-resistance preserving hash function designed using $r$ $tn$-to-$n$-bit compression function calls, we must have $r \geq \lceil (\ell-s)/(t-1) \rceil $. Throughout the paper, all operations other than the compression function are assumed to be linear (which we call linear hash mode).
References
[ABR21]
Elena Andreeva, Rishiraj Bhattacharyya, and Arnab Roy. Compactness of Hashing Modes and Efficiency Beyond Merkle Tree. In Anne Canteaut and François-Xavier Standaert, editors, Advances in Cryptology - EUROCRYPT 2021 - 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, October 17-21, 2021, Proceedings, Part II, volume 12697 of Lecture Notes in Computer Science, pages 92–123. 2021. Springer. DOI: 10.1007/978-3-030-77886-6_4
[Bar68]
Erwin H. Bareiss. Sylvester's Identity and Multistep Integer-Preserving Gaussian Elimination. Mathematics of Computation, 22(103):565–578, 1968.
[BCG+14]
Eli Ben-Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, and Madars Virza. Zerocash: Decentralized Anonymous Payments from Bitcoin. IACR Cryptol. ePrint Arch., 2014.
[BCS09]
John Black, Martin Cochran, and Thomas Shrimpton. On the Impossibility of Highly-Efficient Blockcipher-Based Hash Functions. J. Cryptol., 22(3):311–329, 2009. DOI: 10.1007/s00145-008-9030-1
[BCTV14]
Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, and Madars Virza. Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture. In Kevin Fu and Jaeyeon Jung, editors, Proceedings of the 23rd USENIX Security Symposium, San Diego, CA, USA, August 20-22, 2014, pages 781–796. 2014. USENIX Association.
[BDK+07]
Johannes Buchmann, Erik Dahmen, Elena Klintsevich, Katsuyuki Okeya, and Camille Vuillaume. Merkle Signatures with Virtually Unlimited Signature Capacity. In Proceedings of the 5th International Conference on Applied Cryptography and Network Security, pages 31–45, Berlin, Heidelberg. 2007. Springer-Verlag. DOI: 10.1007/978-3-540-72738-5_3
[BDPA11]
Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche. Duplexing the Sponge: Single-Pass Authenticated Encryption and Other Applications. In Ali Miri and Serge Vaudenay, editors, Selected Areas in Cryptography - 18th International Workshop, SAC 2011, Toronto, ON, Canada, August 11-12, 2011, Revised Selected Papers, volume 7118 of Lecture Notes in Computer Science, pages 320–337. 2011. Springer. DOI: 10.1007/978-3-642-28496-0_19
[BDPVA07]
Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche. Sponge functions. In ECRYPT hash workshop. 2007.
[Ben20]
David Benjamin. Batch Signing for TLS. Technical report number draft-ietf-tls-batch-signing-00, Internet Engineering Task Force. Work in Progress. January 2020.
[BGD+06]
Johannes Buchmann, Luis Carlos Coronado García, Erik Dahmen, Martin Döring, and Elena Klintsevich. CMSS: an improved merkle signature scheme. In Proceedings of the 7th International Conference on Cryptology in India, pages 349–363, Berlin, Heidelberg. 2006. Springer-Verlag. DOI: 10.1007/11941378_25
[BHK+19]
Daniel J. Bernstein, Andreas Hülsing, Stefan Kölbl, Ruben Niederhagen, Joost Rijneveld, and Peter Schwabe. The SPHINCS\({}^{\mbox{+}}\) Signature Framework. In Lorenzo Cavallaro, Johannes Kinder, XiaoFeng Wang, and Jonathan Katz, editors, Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, CCS 2019, London, UK, November 11-15, 2019, pages 2129–2146. 2019. ACM. DOI: 10.1145/3319535.3363229
[BJKS93]
Jürgen Bierbrauer, Thomas Johansson, Gregory Kabatianskii, and Ben J. M. Smeets. On Families of Hash Functions via Geometric Codes and Concatenation. In Douglas R. Stinson, editor, Advances in Cryptology - CRYPTO '93, 13th Annual International Cryptology Conference, Santa Barbara, California, USA, August 22-26, 1993, Proceedings, volume 773 of Lecture Notes in Computer Science, pages 331–342. 1993. Springer. DOI: 10.1007/3-540-48329-2_28
[BRS02]
John Black, Phillip Rogaway, and Thomas Shrimpton. Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV. In Moti Yung, editor, Advances in Cryptology - CRYPTO 2002, 22nd Annual International Cryptology Conference, Santa Barbara, California, USA, August 18-22, 2002, Proceedings, volume 2442 of Lecture Notes in Computer Science, pages 320–335. 2002. Springer. DOI: 10.1007/3-540-45708-9_21
[Dam89]
Ivan Damgård. A Design Principle for Hash Functions. In Gilles Brassard, editor, Advances in Cryptology - CRYPTO '89, 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 1989, Proceedings, volume 435 of Lecture Notes in Computer Science, pages 416–427. 1989. Springer. DOI: 10.1007/0-387-34805-0_39
[DDN22]
Chandranan Dhar, Yevgeniy Dodis, and Mridul Nandi. Revisiting Collision and Local Opening Analysis of ABR Hash. In Dana Dachman-Soled, editor, 3rd Conference on Information-Theoretic Cryptography (ITC 2022), volume 230 of Leibniz International Proceedings in Informatics (LIPIcs), pages 11:1–11:22, Dagstuhl, Germany. 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. DOI: 10.4230/LIPIcs.ITC.2022.11
[DKMN21]
Yevgeniy Dodis, Dmitry Khovratovich, Nicky Mouha, and Mridul Nandi. T5: Hashing Five Inputs with Three Compression Calls. IACR Cryptol. ePrint Arch., 2021.
[GGPR13]
Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova. Quadratic Span Programs and Succinct NIZKs without PCPs. In Thomas Johansson and Phong Q. Nguyen, editors, Advances in Cryptology - EUROCRYPT 2013, 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26-30, 2013. Proceedings, volume 7881 of Lecture Notes in Computer Science, pages 626–645. 2013. Springer. DOI: 10.1007/978-3-642-38348-9_37
[HS91]
Stuart Haber and W. Scott Stornetta. How to Time-Stamp a Digital Document. J. Cryptol., 3(2):99–111, 1991. DOI: 10.1007/BF00196791
[Mer80]
Ralph C. Merkle. Protocols for Public Key Cryptosystems. In Proceedings of the 1980 IEEE Symposium on Security and Privacy, Oakland, California, USA, April 14-16, 1980, pages 122–134. 1980. IEEE Computer Society. DOI: 10.1109/SP.1980.10006
[Mer89]
Ralph C. Merkle. A Certified Digital Signature. In Gilles Brassard, editor, Advances in Cryptology - CRYPTO '89, 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 1989, Proceedings, volume 435 of Lecture Notes in Computer Science, pages 218–238. 1989. Springer. DOI: 10.1007/0-387-34805-0_21
[M.O78]
Rabin M.O.. Digitalized Signatures. Foundations of Secure Computation, 1978.
[Rab79]
M. O. Rabin. DIGITALIZED SIGNATURES AND PUBLIC-KEY FUNCTIONS AS INTRACTABLE AS FACTORIZATION. Technical report, 1979.
[Rog06]
Phillip Rogaway. Formalizing Human Ignorance. In Phong Q. Nguyen, editor, Progressin Cryptology - VIETCRYPT 2006, First International Conference on Cryptology in Vietnam, Hanoi, Vietnam, September 25-28, 2006, Revised Selected Papers, volume 4341 of Lecture Notes in Computer Science, pages 211–228. 2006. Springer. DOI: 10.1007/11958239_14
[RS07]
Thomas Ristenpart and Thomas Shrimpton. How to Build a Hash Function from Any Collision-Resistant Function. In Kaoru Kurosawa, editor, Advances in Cryptology - ASIACRYPT 2007, 13th International Conference on the Theory and Application of Cryptology and Information Security, Kuching, Malaysia, December 2-6, 2007, Proceedings, volume 4833 of Lecture Notes in Computer Science, pages 147–163. 2007. Springer. DOI: 10.1007/978-3-540-76900-2_9
[RS08]
Phillip Rogaway and John P. Steinberger. Constructing Cryptographic Hash Functions from Fixed-Key Blockciphers. In David A. Wagner, editor, Advances in Cryptology - CRYPTO 2008, 28th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2008. Proceedings, volume 5157 of Lecture Notes in Computer Science, pages 433–450. 2008. Springer. DOI: 10.1007/978-3-540-85174-5_24
[SS08]
Thomas Shrimpton and Martijn Stam. Building a Collision-Resistant Compression Function from Non-compressing Primitives. In Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz, editors, Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part II - Track B: Logic, Semantics, and Theory of Programming & Track C: Security and Cryptography Foundations, volume 5126 of Lecture Notes in Computer Science, pages 643–654. 2008. Springer. DOI: 10.1007/978-3-540-70583-3_52
[SSY12]
John P. Steinberger, Xiaoming Sun, and Zhe Yang. Stam's Conjecture and Threshold Phenomena in Collision Resistance. In Reihaneh Safavi-Naini and Ran Canetti, editors, Advances in Cryptology - CRYPTO 2012 - 32nd Annual Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2012. Proceedings, volume 7417 of Lecture Notes in Computer Science, pages 384–405. 2012. Springer. DOI: 10.1007/978-3-642-32009-5_23
[Sta08]
Martijn Stam. Beyond Uniformity: Better Security/Efficiency Tradeoffs for Compression Functions. In David A. Wagner, editor, Advances in Cryptology - CRYPTO 2008, 28th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2008. Proceedings, volume 5157 of Lecture Notes in Computer Science, pages 397–412. 2008. Springer. DOI: 10.1007/978-3-540-85174-5_22
[Ste10]
John P. Steinberger. Stam's Collision Resistance Conjecture. In Henri Gilbert, editor, Advances in Cryptology - EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Monaco / French Riviera, May 30 - June 3, 2010. Proceedings, volume 6110 of Lecture Notes in Computer Science, pages 597–615. 2010. Springer. DOI: 10.1007/978-3-642-13190-5_30
PDF
History
Submitted: 2024-07-08
Accepted: 2024-09-02
Published: 2024-10-07
Accepted: 2024-09-02
Published: 2024-10-07
How to cite
Debasmita Chakraborty and Mridul Nandi, Lower Bound on Number of Compression Calls of a Collision-Resistance Preserving Hash. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/akgy11zn4.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.