IACR News item: 19 February 2016
Peter Gazi, Stefano Tessaro
ePrint Report
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.
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.
Additional news items may be found on the IACR news page.