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)
- 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
-
CC BY