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 cryptographyrandom oraclespermutationsspongeSHA3
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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2021/062}},
      url = {https://eprint.iacr.org/2021/062}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.