Paper 2016/169

Provably Robust Sponge-Based PRNGs and KDFs

Peter Gaži and Stefano Tessaro

Abstract

We study the problem of devising provably secure PRNGs with input based on the sponge paradigm. Such constructions are very appealing, as efficient software/hardware implementations of SHA-3 can easily be translated into a PRNG in a nearly black-box way. The only existing sponge-based construction, proposed by Bertoni et al. (CHES 2010), fails to achieve the security notion of robustness recently considered by Dodis et al. (CCS 2013), for two reasons: (1) The construction is deterministic, and thus there are high-entropy input distributions on which the construction fails to extract random bits, and (2) The construction is not forward secure, and presented solutions aiming at restoring forward security have not been rigorously analyzed. We propose a seeded variant of Bertoni et al.'s PRNG with input which we prove secure in the sense of robustness, delivering in particular concrete security bounds. On the way, we make what we believe to be an important conceptual contribution, developing a variant of the security framework of Dodis et al. tailored at the ideal permutation model that captures PRNG security in settings where the weakly random inputs are provided from a large class of possible adversarial samplers which are also allowed to query the random permutation. As a further application of our techniques, we also present a simple and very efficient key-derivation function based on sponges (which can hence be instantiated from SHA-3 in a black-box fashion), which we also prove secure when fed with samples from permutation-dependent distributions.

Metadata
Available format(s)
PDF
Publication info
A major revision of an IACR publication in Eurocrypt 2016
Keywords
PRNGsspongesSHA-3key derivationweak randomness
Contact author(s)
peter gazi @ ist ac at
History
2016-02-19: received
Short URL
https://ia.cr/2016/169
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/169,
      author = {Peter Gaži and Stefano Tessaro},
      title = {Provably Robust Sponge-Based PRNGs and KDFs},
      howpublished = {Cryptology ePrint Archive, Paper 2016/169},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/169}},
      url = {https://eprint.iacr.org/2016/169}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.