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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A minor revision of an IACR publication in FSE 2016
Keywords
PRFXOFgame playingcoefficient H techniquelazy samplingmulti-collisionStirling's approximation
Contact author(s)
Naito Yusuke @ ce mitsubishielectric co jp
History
2016-03-17: received
Short URL
https://ia.cr/2016/292
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/292,
      author = {Yusuke Naito and Kan Yasuda},
      title = {New Bounds for Keyed Sponges with Extendable Output: Independence between Capacity and Message Length},
      howpublished = {Cryptology ePrint Archive, Paper 2016/292},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/292}},
      url = {https://eprint.iacr.org/2016/292}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.