Indifferentiability of the Sponge Hash Family: New Attacks and the Optimal Construction

The sponge construction is subject to an indifferentiability security bound of c/2 bits, where c denotes the capacity. For a given b-bit permutation, the sponge construction allows sacrificing the rate r = b − c to achieve the theoretically optimal security bound of (b−1)/2 bits. However, the efficient construction of a permutationbased hash with b/2-bit security remains an open problem.In this paper, we analyze the porifera family, a class of generalized sponge functions including existing designs such as JH and FP. We introduce the t-way chosen multitarget (t-CMT) preimage resistance and propose the Universal San Mai Attack (USMA) to target this property. We reduce the indifferentiability bound for both JH and FP to b/3 bits, which is lower than previously assumed.Furthermore, we classify the porifera family and prove that, under a restriction on the linear layer complexity, there exists a unique design, named VFB, that achieves the optimal security bound of approximately b/2 bits. Although it requires r ≥ c and a distinct finalization, it provides higher throughput for high-security parameters. For instance, using a 1600-bit permutation, VFB achieves 512-bit security at a rate of 1064 bits, exceeding the rate of Keccak-512.