Cryptology ePrint Archive: Report 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.

Category / Keywords: secret-key cryptography / PRF, XOF, game playing, coefficient H technique, lazy sampling, multi-collision, Stirling's approximation

Original Publication (with minor differences): IACR-FSE-2016

Date: received 16 Mar 2016, last revised 16 Mar 2016

Contact author: Naito Yusuke at ce MitsubishiElectric co jp

Available format(s): PDF | BibTeX Citation

Version: 20160317:161734 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]