Paper 2021/062 Original: eprint.iacr.org/2021/062 ↗
Compressed Permutation Oracles (And the Collision-Resistance of Sponge/SHA3)
Abstract
We generalize Zhandry's compressed oracle technique to invertible random permutations. (That is, to a quantum random oracle where the adversary has access to a random permutation and its inverse.) This enables security proofs with lazy sampling, i.e., where oracle outputs are chosen only when needed. As an application of our technique, we show the collision-resistance of the sponge construction based on invertible permutations. In particular, this shows the collision-resistance of SHA3 (in the random oracle model).
Metadata
- Available format(s)
PDF- Category
- Foundations
- Publication info
- Preprint.
- History
- 2021-12-02: last updated
- 2021-01-18: published
- Short URL
- https://ia.cr/2021/062
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2021/062,
author = {Dominique Unruh},
title = {Compressed Permutation Oracles (And the Collision-Resistance of Sponge/SHA3)},
howpublished = {Cryptology {ePrint} Archive, Paper 2021/062},
year = {2021},
url = {https://eprint.iacr.org/2021/062}
}