Compressed Permutation Oracles (And the Collision-Resistance of Sponge/SHA3)

Dominique Unruh

Paper 2021/062

Compressed Permutation Oracles (And the Collision-Resistance of Sponge/SHA3)

Dominique Unruh

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).

Note: Version 2: Added erratum describing an error in the paper. Version 3: Reuploaded because previous version was compiled with draft-option. (Content not changed.)

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint. MINOR revision.
Keywords: Post-quantum cryptography random oracles permutations sponge SHA3
Contact author(s): unruh @ ut ee
History: 2021-12-02: last of 2 revisions; 2021-01-18: received; See all versions
Short URL: https://ia.cr/2021/062
License: CC BY

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}
}