Paper 2023/217

Indifferentiability of the Sponge Construction with a Restricted Number of Message Blocks

Abstract

The sponge construction is a popular method for hashing. Quickly after its introduction, the sponge was proven to be tightly indifferentiable from a random oracle up to $\approx 2^{c/2}$ queries, where $c$ is the capacity. However, this bound is not tight when the number of message blocks absorbed is restricted to $\ell <\lceil \frac{c}{2(b-c)}\rceil +1$ (but still an arbitrary number of blocks can be squeezed). In this work, we show that this restriction leads to indifferentiability from a random oracle up to $\approx min\{2^{b/2},max\{2^{c/2},2^{b-\ell \times (b-c)}\}\}$ queries, where $b>c$ is the permutation size. Depending on the parameters chosen, this result allows to have enhanced security or to absorb at a larger rate for applications that require a fixed-length input hash function.