Post-quantum security of the sponge construction. (English) Zbl 1426.81031

Lange, Tanja (ed.) et al., Post-quantum cryptography. 9th international conference, PQCrypto 2018, Fort Lauderdale, FL, USA, April 9–11, 2018. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10786, 185-204 (2018).
Summary: 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.
For the entire collection see [Zbl 1387.94005].


81P94 Quantum cryptography (quantum-theoretic aspects)
94A62 Authentication, digital signatures and secret sharing


spongent; PHOTON; Quark
Full Text: DOI Link