Séminaire

Date : 26 novembre 2025 11:00 - Salle :salle A001 Permutation-Based Hashing With Stronger (Second) Preimage Resistance Charlotte LEFEVRE - Radboud Unbiversity

The sponge is a popular construction of hash function design. It operates with a b-bit permutation on a b-bit state, that is split into a c-bit inner part and an r-bit outer part. However, the security bounds of the sponge are most often dominated by the capacity c: if the length of the digest is n bits, the construction tightly achieves min{n/2,c/2}-bit collision resistance, min{n,c/2}-bit second preimage resistance, and min{n,max{n-r,c/2}}-bit preimage resistance. Here, it is noteworthy that the generic attacks matching the preimage and second preimage bounds make use of the inverse of the permutation.

We demonstrate that, by a relatively simple adjustment, significantly improved preimage and second preimage resistance can be achieved. In detail, we first present the sponge-dm construction, that differs from the sponge by evaluating the permutation during absorption in a Davies-Meyer mode. This construction generically achieves min{n/2,c/2}-bit collision resistance as the sponge does, but n-bit preimage resistance and min{n,c-log_2(\alpha)}-bit second preimage resistance, where \alpha is the maximum size of the first preimage in blocks. Next, we investigate how improved security can be achieved with a smaller feed-forward, and we present the sponge-edm^a family of functions, indexed by a parameter a in {0,..,b}. These functions replace the permutation during absorption in the sponge by an Encrypted Davies-Meyer mode, but with only a bits of feed-forward. For a=b, comparable bounds as for sponge-dm are obtained, and these bounds gradually decrease to the original sponge bounds for decreasing values of a.

We finally discuss how these improvements directly strengthen hash-based signature schemes whose security relies solely on the (second) preimage resistance of the underlying hash functions.

https://charlotte-lefevre.github.io/ 

https://scholar.google.com/citations?user=wmzZzjIAAAAJ&hl=en