Provably robust sponge-based PRNGs and KDFs

Gazi P, Tessaro S. 2016. Provably robust sponge-based PRNGs and KDFs. EUROCRYPT: Theory and Applications of Cryptographic Techniques, LNCS, vol. 9665, 87–116.


Conference Paper | Published | English

Scopus indexed
Author
Gazi, PeterISTA; Tessaro, Stefano
Department
Series Title
LNCS
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 an efficient sponge-based key-derivation function (which can be instantiated from SHA-3 in a black-box fashion), which we also prove secure when fed with samples from permutation-dependent distributions.
Publishing Year
Date Published
2016-05-01
Publisher
Springer
Volume
9665
Page
87 - 116
Conference
EUROCRYPT: Theory and Applications of Cryptographic Techniques
Conference Location
Vienna, Austria
Conference Date
2016-05-08 – 2016-05-12
IST-REx-ID

Cite this

Gazi P, Tessaro S. Provably robust sponge-based PRNGs and KDFs. In: Vol 9665. Springer; 2016:87-116. doi:10.1007/978-3-662-49890-3_4
Gazi, P., & Tessaro, S. (2016). Provably robust sponge-based PRNGs and KDFs (Vol. 9665, pp. 87–116). Presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Vienna, Austria: Springer. https://doi.org/10.1007/978-3-662-49890-3_4
Gazi, Peter, and Stefano Tessaro. “Provably Robust Sponge-Based PRNGs and KDFs,” 9665:87–116. Springer, 2016. https://doi.org/10.1007/978-3-662-49890-3_4.
P. Gazi and S. Tessaro, “Provably robust sponge-based PRNGs and KDFs,” presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Vienna, Austria, 2016, vol. 9665, pp. 87–116.
Gazi P, Tessaro S. 2016. Provably robust sponge-based PRNGs and KDFs. EUROCRYPT: Theory and Applications of Cryptographic Techniques, LNCS, vol. 9665, 87–116.
Gazi, Peter, and Stefano Tessaro. Provably Robust Sponge-Based PRNGs and KDFs. Vol. 9665, Springer, 2016, pp. 87–116, doi:10.1007/978-3-662-49890-3_4.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar