Cryptology ePrint Archive: Report 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).

Category / Keywords: foundations / Post-quantum cryptography, random oracles, permutations, sponge, SHA3

Date: received 16 Jan 2021, last revised 22 Feb 2021

Contact author: unruh at ut ee

Available format(s): PDF | BibTeX Citation

Note: Added erratum describing an error in the paper.

Version: 20210222:165919 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]