Paper 2025/963
Permutation-Based Hashing with Stronger (Second) Preimage Resistance - Application to Hash-Based Signature Schemes
Siwei Sun, School of Cryptology, University of Chinese Academy of Sciences, China
Shun Li, School of Cryptology, University of Chinese Academy of Sciences, China
Zhiyu Zhang, School of Cryptology, University of Chinese Academy of Sciences, China
Charlotte Lefevre, Digital Security Group, Radboud University, Nijmegen, The Netherlands
Bart Mennink, Digital Security Group, Radboud University, Nijmegen, The Netherlands
Zhen Qin, School of Cryptology, University of Chinese Academy of Sciences, China
Dengguo Feng, State Key Laboratory of Cryptology, China
Abstract
The sponge is a popular construction of hash function design. It operates with a -bit permutation on a -bit state, that is split into a -bit inner part and an -bit outer part. However, the security bounds of the sponge are most often dominated by the capacity : If the length of the digest is bits, the construction achieves -bit collision resistance and -bit second preimage resistance (and a slightly more complex but similar bound for preimage resistance). In certain settings, these bounds are too restrictive. For example, the recently announced Chinese call for a new generation of cryptographic algorithms expects hash functions with 1024-bit digests and 1024-bit preimage and second preimage resistance, rendering the classical sponge design basically unusable, except with an excessively large permutation. We present the SPONGE-DM construction to salvage the sponge in these settings. This construction differs from the sponge by evaluating the permutation during absorption in a Davies-Meyer mode. We also present SPONGE-EDM, that evaluates potentially round-reduced permutations during absorption in Encrypted Davies-Meyer mode, and SPONGE-EDM, that optimizes the amount of feed-forward data in this construction. We prove that these constructions generically achieve -bit collision resistance as the sponge does, but they achieve -bit preimage resistance and -bit second preimage resistance, where is the maximum size of the first preimage in blocks. With such constructions, one could improve the security (resp., efficiency) without sacrificing the efficiency (resp., security) of hash-based signature schemes whose security relies solely on the (second) preimage resistance of the underlying hash functions. Also, one could use the -bit Keccak permutation with capacity and rate to achieve -bit collision resistance and -bit preimage and second preimage resistance, without making extra permutation calls. To encourage further cryptanalysis, we propose two concrete families of instances of SPONGE-EDM (expected to be weaker than SPONGE-DM), using SHA3 and Ascon. Moreover, we concretely demonstrate the security and performance advantages of these instances in the context of hashing and hash-based signing.
PDF
