Paper 2016/292

New Bounds for Keyed Sponges with Extendable Output: Independence between Capacity and Message Length

Yusuke Naito and Kan Yasuda

Abstract

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ži~et~al. at CRYPTO~2015. Our bound is essentially tight, matching the two types of attacks pointed out by Gaži~et~al. For the case $c>b/2$, Gaž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.