Welcome to the resource topic for 2024/407
Title:
Permutation-Based Hashing Beyond the Birthday Bound
Authors: Charlotte Lefevre, Bart Mennink
Abstract:It is known that the sponge construction is tightly indifferentiable from a random oracle up to around 2^{c/2} queries, where c is the capacity. In particular, it cannot provide generic security better than half of the underlying permutation size. In this paper, we aim to achieve hash function security beating this barrier. We present a hashing mode based on two b-bit permutations named the double sponge. The double sponge can be seen as the sponge embedded within the double block length hashing paradigm, making two permutation calls in parallel interleaved with an efficient mixing function. Similarly to the sponge, the permutation size is split as b = r+c, and the underlying compression function absorbs r bits at a time. We prove that the double sponge is indifferentiable from a random oracle up to around 2^{2c/3} queries. This means that the double sponge achieves security beyond the birthday bound in the capacity. In addition, if c>3b/4, the double sponge beats the birthday bound in the primitive size, to our knowledge being the first hashing mode based on a permutation that accomplices this feature.
ePrint: https://eprint.iacr.org/2024/407
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .