International Association
for Cryptologic Research

We provide new bounds for the pseudo-random function security of keyed sponge constructions. For the case $c\leq 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 Ga\v{z}i~et~al. at CRYPTO~2015. Our bound is essentially tight, matching the two types of attacks pointed out by Ga\v{z}i~et~al. For the case $c>b/2$, Ga\v{z}i~et~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 Mennink~et~al.'s bound presented at ASIACRYPT~2015.