New Bounds for Keyed Sponges with Extendable Output: Independence Between Capacity and Message Length
We provide new bounds for the pseudo random function security of keyed sponge constructions. For the case $c\le b/2$$c the capacity and b the permutation size, our result improves over all previously known bounds. A remarkable aspect of our bound is that dependence between capacity and message length is removed, partially solving the open problem posed by Gazii 3/4 ?eti 3/4 ?al. at CRYPTOi 3/4 ?2015. Our bound is essentially tight, matching the two types of attacks pointed out by Gazii 3/4 ?eti 3/4 ?al. For the case $c>b/2$ Gazii 3/4 ?eti 3/4 ?al.'s bound remains the best for the case of single block output, but for keyed sponges with extendable outputs, our result partly when query complexity is relatively large provides better security than Menninki 3/4 ?eti 3/4 ?al.'s bound presented at ASIACRYPTi 3/4 ?2015.
FSE