Post-quantum security of the sponge construction

Jan Czajkowski, Leon Groot Bruinderink, Andreas Hülsing, Christian Schaffner, Dominique Unruh

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

17 Citations (Scopus)


We investigate the post-quantum security of hash functions based on the sponge construction. A crucial property for hash functions in the post-quantum setting is the collapsing property (a strengthening of collision-resistance). We show that the sponge construction is collapsing (and in consequence quantum collision-resistant) under suitable assumptions about the underlying block function. In particular, if the block function is a random function or a (non-invertible) random permutation, the sponge construction is collapsing. We also give a quantum algorithm for finding collisions in an arbitrary function. For the sponge construction, the algorithm complexity asymptotically matches the complexity implied by collision resistance.

Original languageEnglish
Title of host publicationPost-Quantum Cryptography - 9th International Conference, PQCrypto 2018, Proceedings
Number of pages20
ISBN (Print)9783319790626
Publication statusPublished - 1 Jan 2018
EventPost-Quantum Cryptography : 9th International Conference, PQCrypto 2018 - Fort Lauderdale, United States
Duration: 9 Apr 201811 Apr 2018
Conference number: 9

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10786 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferencePost-Quantum Cryptography
Abbreviated titlePQCrypto 2018
Country/TerritoryUnited States
CityFort Lauderdale


  • Collapsing
  • Collision resistance
  • QROM
  • Quantum algorithms
  • Sponge construction


Dive into the research topics of 'Post-quantum security of the sponge construction'. Together they form a unique fingerprint.

Cite this