Cryptology ePrint Archive: Report 2017/302

Quantum preimage, 2nd-preimage, and collision resistance of SHA3

Jan Czajkowski and Leon Groot Bruinderink and Andreas Hülsing and Christian Schaffner

Abstract: SHA3 and its extendable output variant SHAKE belong to the family of sponge functions. In this work, we present formal security arguments for the quantum preimage, $2^{\text{nd}}$-preimage, and collision resistance of any sponge function. We just assume that the internally used transformation behaves like a random transformation. These are the first formal arguments that sponge functions (incl. SHA3 and SHAKE) are secure in the post-quantum setting.

We even go one step further and prove that sponges are collapsing (Unruh, EUROCRYPT'16). Thereby, we can also derive the applicability of sponge functions for collapse-binding commitments.

In addition to the security arguments, we also present a quantum collision attack against sponges. The complexity of our attack asymptotically matches the proven lower bound up to a square root.

Category / Keywords: Post-quantum cryptography; SHA3, SHAKE, sponges, keccak, hash function, quantum security, quantum collision resistance, quantum second-preimage resistance, quantum preimage resistance

Date: received 4 Apr 2017, last revised 9 Apr 2017

Contact author: authors-quantum-sponges at huelsing net

Available format(s): PDF | BibTeX Citation

Version: 20170410:133825 (All versions of this report)

Short URL: ia.cr/2017/302

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]