Compactness of hashing modes and efficiency beyond Merkle tree. (English) Zbl 1479.94114
Canteaut, Anne (ed.) et al., 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. Cham: Springer. Lect. Notes Comput. Sci. 12697, 92-123 (2021).
Summary: 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 T. Shrimpton and M. Stam [Lect. Notes Comput. Sci. 5126, 643–654 (2008; Zbl 1155.94387)], P. Rogaway and J. Steinberger [ibid. 5157, 433–450 (2008; Zbl 1183.94047)], and B. Mennink and B. Preneel [ibid. 7417, 330–347 (2012; Zbl 1296.94132)] 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.
To enable efficiency analysis and comparison across hash functions built from primitives of different domain sizes, in this work we propose the new 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 [M. Stam, ibid. 5157, 397–412 (2008; Zbl 1183.68279)] to obtain maximal efficiency.
i) We then present two tree-based modes of operation as a design principle for compact, large domain, fixed-input-length hash functions. Our first construction is an Augmented Binary Tree (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 \(\ell \ge 2\). 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.
ii) With our second design we focus our attention on the indifferentiability security notion. While the ABR mode achieves collision resistance, it fails to achieve indifferentiability from a random oracle within \(2^{n/3}\) queries. ABR\textsuperscript{+} 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.
Both of our designs are closely related to the ubiquitous Merkle Trees and have the potential for real-world applicability where the speed of hashing is of primary interest.
For the entire collection see [Zbl 1475.94011].
To enable efficiency analysis and comparison across hash functions built from primitives of different domain sizes, in this work we propose the new 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 [M. Stam, ibid. 5157, 397–412 (2008; Zbl 1183.68279)] to obtain maximal efficiency.
i) We then present two tree-based modes of operation as a design principle for compact, large domain, fixed-input-length hash functions. Our first construction is an Augmented Binary Tree (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 \(\ell \ge 2\). 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.
ii) With our second design we focus our attention on the indifferentiability security notion. While the ABR mode achieves collision resistance, it fails to achieve indifferentiability from a random oracle within \(2^{n/3}\) queries. ABR\textsuperscript{+} 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.
Both of our designs are closely related to the ubiquitous Merkle Trees and have the potential for real-world applicability where the speed of hashing is of primary interest.
For the entire collection see [Zbl 1475.94011].
References:
| [1] | http://bittorrent.org/beps/bep_0030.html |
| [2] | Andreeva, E., Bhattacharyya, R., Roy, A.: Compactness of hashing modes and efficiency beyond Merkle tree. IACR Cryptol. ePrint Arch. (2021) · Zbl 1479.94114 |
| [3] | Andreeva, E.; Mennink, B.; Preneel, B.; Garay, JA; De Prisco, R., On the indifferentiability of the Grøstl hash function, Security and Cryptography for Networks, 88-105 (2010), Heidelberg: Springer, Heidelberg · Zbl 1285.94039 · doi:10.1007/978-3-642-15317-4_7 |
| [4] | Andreeva, E.; Mennink, B.; Preneel, B.; Burmester, M.; Tsudik, G.; Magliveras, S.; Ilić, I., Security reductions of the second round SHA-3 candidates, Information Security, 39-53 (2011), Heidelberg: Springer, Heidelberg · Zbl 1371.94619 · doi:10.1007/978-3-642-18178-8_5 |
| [5] | Andreeva, E.; Mennink, B.; Preneel, B., The parazoa family: generalizing the sponge hash functions, Int. J. Inf. Sec., 11, 3, 149-165 (2012) · doi:10.1007/s10207-012-0157-6 |
| [6] | Ben-Sasson, E., Zerocash: decentralized anonymous payments from bitcoin, IACR Cryptol. ePrint Arch., 2014, 349 (2014) |
| [7] | Ben-Sasson, E., Chiesa, A., Tromer, E., Virza, M.: Succinct non-interactive zero knowledge for a von Neumann architecture. In: Fu, K., Jung, J. (eds.) USENIX Security 2014, pp. 781-796. USENIX Association (August 2014) · Zbl 1334.68077 |
| [8] | Benjamin, D.: Batch signing for TLS (2019). https://tools.ietf.org/html/draft-davidben-tls-batch-signing-02 |
| [9] | Bernstein, D.J., Hülsing, A., Kölbl, S., Niederhagen, R., Rijneveld, J., Schwabe, P.: The \(SPHINCS^+\) signature framework. In: ACM CCS 2019, pp. 2129-2146. ACM Press (November 2019) |
| [10] | Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: Duplexing the sponge: single-pass authenticated encryption and other applications. Cryptology ePrint Archive, Report 2011/499 (2011). http://eprint.iacr.org/2011/499 · Zbl 1292.94030 |
| [11] | Bertoni, G.; Daemen, J.; Peeters, M.; Van Assche, G.; Johansson, T.; Nguyen, PQ, Keccak, Advances in Cryptology - EUROCRYPT 2013, 313-314 (2013), Heidelberg: Springer, Heidelberg · Zbl 1306.94028 · doi:10.1007/978-3-642-38348-9_19 |
| [12] | Bertoni, G.; Daemen, J.; Peeters, M.; Van Assche, G.; Smart, N., On the indifferentiability of the sponge construction, Advances in Cryptology - EUROCRYPT 2008, 181-197 (2008), Heidelberg: Springer, Heidelberg · Zbl 1149.94304 · doi:10.1007/978-3-540-78967-3_11 |
| [13] | Bertoni, G.; Daemen, J.; Peeters, M.; Van Assche, G.; Miri, A.; Vaudenay, S., Duplexing the sponge: single-pass authenticated encryption and other applications, Selected Areas in Cryptography, 320-337 (2012), Heidelberg: Springer, Heidelberg · Zbl 1292.94030 · doi:10.1007/978-3-642-28496-0_19 |
| [14] | Black, J.; Cochran, M.; Shrimpton, T.; Cramer, R., On the impossibility of highly-efficient Blockcipher-based hash functions, Advances in Cryptology - EUROCRYPT 2005, 526-541 (2005), Heidelberg: Springer, Heidelberg · Zbl 1137.94339 · doi:10.1007/11426639_31 |
| [15] | Black, J.; Rogaway, P.; Shrimpton, T.; Yung, M., Black-box analysis of the block-cipher-based hash-function constructions from PGV, Advances in Cryptology — CRYPTO 2002, 320-335 (2002), Heidelberg: Springer, Heidelberg · Zbl 1026.94522 · doi:10.1007/3-540-45708-9_21 |
| [16] | Bogdanov, A.; Knežević, M.; Leander, G.; Toz, D.; Varıcı, K.; Verbauwhede, I.; Preneel, B.; Takagi, T., spongent: A Lightweight Hash Function, Cryptographic Hardware and Embedded Systems - CHES 2011, 312-325 (2011), Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-642-23951-9_21 |
| [17] | BSI. https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publications/TechGuidelines/TR03125/TR-03125_M3_v1_2_2.pdf |
| [18] | Buchmann, J.; Dahmen, E.; Klintsevich, E.; Okeya, K.; Vuillaume, C.; Katz, J.; Yung, M., Merkle signatures with virtually unlimited signature capacity, Applied Cryptography and Network Security, 31-45 (2007), Heidelberg: Springer, Heidelberg · Zbl 1214.94060 · doi:10.1007/978-3-540-72738-5_3 |
| [19] | Buchmann, J.; García, LCC; Dahmen, E.; Döring, M.; Klintsevich, E.; Barua, R.; Lange, T., CMSS - an improved Merkle signature scheme, Progress in Cryptology - INDOCRYPT 2006, 349-363 (2006), Heidelberg: Springer, Heidelberg · Zbl 1175.94106 · doi:10.1007/11941378_25 |
| [20] | Chen, S.; Steinberger, J.; Nguyen, PQ; Oswald, E., Tight security bounds for key-alternating ciphers, Advances in Cryptology - EUROCRYPT 2014, 327-350 (2014), Heidelberg: Springer, Heidelberg · Zbl 1317.94096 · doi:10.1007/978-3-642-55220-5_19 |
| [21] | Damgård, IB; Brassard, G., A design principle for hash functions, Advances in Cryptology — CRYPTO’ 89 Proceedings, 416-427 (1990), New York: Springer, New York · Zbl 0724.68029 · doi:10.1007/0-387-34805-0_39 |
| [22] | Gennaro, R.; Gentry, C.; Parno, B.; Raykova, M.; Johansson, T.; Nguyen, PQ, Quadratic span programs and succinct NIZKs without PCPs, Advances in Cryptology - EUROCRYPT 2013, 626-645 (2013), Heidelberg: Springer, Heidelberg · Zbl 1300.94056 · doi:10.1007/978-3-642-38348-9_37 |
| [23] | Haber, S.; Stornetta, WS, How to time-stamp a digital document, J. Cryptol., 3, 2, 99-111 (1991) · Zbl 0800.68408 · doi:10.1007/BF00196791 |
| [24] | Maurer, U.; Renner, R.; Holenstein, C.; Naor, M., Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology, Theory of Cryptography, 21-39 (2004), Heidelberg: Springer, Heidelberg · Zbl 1197.94196 · doi:10.1007/978-3-540-24638-1_2 |
| [25] | Mennink, B.; Preneel, B.; Safavi-Naini, R.; Canetti, R., Hash functions based on three permutations: a generic security analysis, Advances in Cryptology - CRYPTO 2012, 330-347 (2012), Heidelberg: Springer, Heidelberg · Zbl 1296.94132 · doi:10.1007/978-3-642-32009-5_20 |
| [26] | Mennink, B.; Preneel, B., Efficient parallelizable hashing using small non-compressing primitives, Int. J. Inf. Secur., 15, 3, 285-300 (2015) · doi:10.1007/s10207-015-0288-7 |
| [27] | Merkle, R.C.: Protocols for public key cryptosystems. In: Proceedings of the 1980 IEEE Symposium on Security and Privacy, Oakland, California, USA, 14-16 April 1980, pp. 122-134. IEEE Computer Society (1980) |
| [28] | Merkle, RC; Brassard, G., A certified digital signature, Advances in Cryptology — CRYPTO’ 89 Proceedings, 218-238 (1990), New York: Springer, New York · doi:10.1007/0-387-34805-0_21 |
| [29] | Nandi, M.; Barua, R.; Lange, T., A simple and unified method of proving indistinguishability, Progress in Cryptology - INDOCRYPT 2006, 317-334 (2006), Heidelberg: Springer, Heidelberg · Zbl 1175.94115 · doi:10.1007/11941378_23 |
| [30] | Patarin, J.; Avanzi, RM; Keliher, L.; Sica, F., The “Coefficients H” technique, Selected Areas in Cryptography, 328-345 (2009), Heidelberg: Springer, Heidelberg · Zbl 1256.94060 · doi:10.1007/978-3-642-04159-4_21 |
| [31] | Ristenpart, T.; Shacham, H.; Shrimpton, T.; Paterson, KG, Careful with composition: limitations of the indifferentiability framework, Advances in Cryptology - EUROCRYPT 2011, 487-506 (2011), Heidelberg: Springer, Heidelberg · Zbl 1290.94155 · doi:10.1007/978-3-642-20465-4_27 |
| [32] | Ristenpart, T.; Shrimpton, T.; Kurosawa, K., How to build a hash function from any collision-resistant function, Advances in Cryptology - ASIACRYPT 2007, 147-163 (2007), Heidelberg: Springer, Heidelberg · Zbl 1153.94425 · doi:10.1007/978-3-540-76900-2_9 |
| [33] | Rivest, RL; Schuldt, JCN, Spritz - a spongy RC4-like stream cipher and hash function, IACR Cryptol. ePrint Arch., 2016, 856 (2016) |
| [34] | Rogaway, P.; Steinberger, J.; Wagner, D., Constructing cryptographic hash functions from fixed-key blockciphers, Advances in Cryptology - CRYPTO 2008, 433-450 (2008), Heidelberg: Springer, Heidelberg · Zbl 1183.94047 · doi:10.1007/978-3-540-85174-5_24 |
| [35] | Rogaway, P.; Steinberger, J.; Smart, N., Security/efficiency tradeoffs for permutation-based hashing, Advances in Cryptology - EUROCRYPT 2008, 220-236 (2008), Heidelberg: Springer, Heidelberg · Zbl 1149.94328 · doi:10.1007/978-3-540-78967-3_13 |
| [36] | Shrimpton, T.; Stam, M.; Aceto, L.; Damgård, I.; Goldberg, LA; Halldórsson, MM; Ingólfsdóttir, A.; Walukiewicz, I., Building a collision-resistant compression function from non-compressing primitives, Automata, Languages and Programming, 643-654 (2008), Heidelberg: Springer, Heidelberg · Zbl 1155.94387 · doi:10.1007/978-3-540-70583-3_52 |
| [37] | Stam, M.; Wagner, D., Beyond uniformity: better security/efficiency tradeoffs for compression functions, Advances in Cryptology - CRYPTO 2008, 397-412 (2008), Heidelberg: Springer, Heidelberg · Zbl 1183.68279 · doi:10.1007/978-3-540-85174-5_22 |
| [38] | Steinberger, J.; Gilbert, H., Stam’s collision resistance conjecture, Advances in Cryptology - EUROCRYPT 2010, 597-615 (2010), Heidelberg: Springer, Heidelberg · Zbl 1280.94094 · doi:10.1007/978-3-642-13190-5_30 |
| [39] | Steinberger, J.; Sun, X.; Yang, Z.; Safavi-Naini, R.; Canetti, R., Stam’s conjecture and threshold phenomena in collision resistance, Advances in Cryptology - CRYPTO 2012, 384-405 (2012), Heidelberg: Springer, Heidelberg · Zbl 1296.94141 · doi:10.1007/978-3-642-32009-5_23 |
| [40] | Wagner, D.; Yung, M., A generalized birthday problem, Advances in Cryptology — CRYPTO 2002, 288-304 (2002), Heidelberg: Springer, Heidelberg · Zbl 1026.94541 · doi:10.1007/3-540-45708-9_19 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
