Post-quantum security of the sponge construction

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

doi:10.1007/978-3-319-79063-3_9

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 proceeding › Conference contribution › Academic › peer-review

18 Citations (Scopus)

Abstract

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 language	English
Title of host publication	Post-Quantum Cryptography - 9th International Conference, PQCrypto 2018, Proceedings
Publisher	Springer
Pages	185-204
Number of pages	20
ISBN (Print)	9783319790626
DOIs	https://doi.org/10.1007/978-3-319-79063-3_9
Publication status	Published - 1 Jan 2018
Event	Post-Quantum Cryptography : 9th International Conference, PQCrypto 2018 - Fort Lauderdale, United States Duration: 9 Apr 2018 → 11 Apr 2018 Conference number: 9

Publication series

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

Conference

Conference	Post-Quantum Cryptography
Abbreviated title	PQCrypto 2018
Country/Territory	United States
City	Fort Lauderdale
Period	9/04/18 → 11/04/18

Funding

This work was supported in part by the Commission of the European Communities through the Horizon 2020 program under project number 645622 PQCRYPTO. CS and JC are supported by a NWO VIDI grant (Project No. 639.022.519). DU was supported by institutional research funding IUT2-1 of the Estonian Ministry of Education and Research, and by the Estonian Centre of Exellence in IT (EXCITE) funded by the ERDF, and the Estonian ICT program 2011–2015 (3.2.1201.13-0022).

Keywords

Collapsing
Collision resistance
QROM
Quantum algorithms
Sponge construction

Access to Document

10.1007/978-3-319-79063-3_9

Cite this

Czajkowski, J., Groot Bruinderink, L., Hülsing, A., Schaffner, C., & Unruh, D. (2018). Post-quantum security of the sponge construction. In Post-Quantum Cryptography - 9th International Conference, PQCrypto 2018, Proceedings (pp. 185-204). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10786 LNCS). Springer. https://doi.org/10.1007/978-3-319-79063-3_9

Czajkowski, Jan ; Groot Bruinderink, Leon ; Hülsing, Andreas et al. / Post-quantum security of the sponge construction. Post-Quantum Cryptography - 9th International Conference, PQCrypto 2018, Proceedings. Springer, 2018. pp. 185-204 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{43dcc7d27fd446dbaac76ee035c98ffd,

title = "Post-quantum security of the sponge construction",

abstract = "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.",

keywords = "Collapsing, Collision resistance, QROM, Quantum algorithms, Sponge construction",

author = "Jan Czajkowski and {Groot Bruinderink}, Leon and Andreas H{\"u}lsing and Christian Schaffner and Dominique Unruh",

year = "2018",

month = jan,

day = "1",

doi = "10.1007/978-3-319-79063-3_9",

language = "English",

isbn = "9783319790626",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "185--204",

booktitle = "Post-Quantum Cryptography - 9th International Conference, PQCrypto 2018, Proceedings",

address = "Germany",

note = "Post-Quantum Cryptography : 9th International Conference, PQCrypto 2018, PQCrypto 2018 ; Conference date: 09-04-2018 Through 11-04-2018",

}

Czajkowski, J, Groot Bruinderink, L, Hülsing, A, Schaffner, C & Unruh, D 2018, Post-quantum security of the sponge construction. in Post-Quantum Cryptography - 9th International Conference, PQCrypto 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10786 LNCS, Springer, pp. 185-204, Post-Quantum Cryptography , Fort Lauderdale, Florida, United States, 9/04/18. https://doi.org/10.1007/978-3-319-79063-3_9

Post-quantum security of the sponge construction. / Czajkowski, Jan; Groot Bruinderink, Leon; Hülsing, Andreas et al.
Post-Quantum Cryptography - 9th International Conference, PQCrypto 2018, Proceedings. Springer, 2018. p. 185-204 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10786 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Post-quantum security of the sponge construction

AU - Czajkowski, Jan

AU - Groot Bruinderink, Leon

AU - Hülsing, Andreas

AU - Schaffner, Christian

AU - Unruh, Dominique

N1 - Conference code: 9

PY - 2018/1/1

Y1 - 2018/1/1

N2 - 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.

AB - 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.

KW - Collapsing

KW - Collision resistance

KW - QROM

KW - Quantum algorithms

KW - Sponge construction

UR - http://www.scopus.com/inward/record.url?scp=85045403878&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-79063-3_9

DO - 10.1007/978-3-319-79063-3_9

M3 - Conference contribution

AN - SCOPUS:85045403878

SN - 9783319790626

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 185

EP - 204

BT - Post-Quantum Cryptography - 9th International Conference, PQCrypto 2018, Proceedings

PB - Springer

T2 - Post-Quantum Cryptography

Y2 - 9 April 2018 through 11 April 2018

ER -

Czajkowski J, Groot Bruinderink L, Hülsing A, Schaffner C, Unruh D. Post-quantum security of the sponge construction. In Post-Quantum Cryptography - 9th International Conference, PQCrypto 2018, Proceedings. Springer. 2018. p. 185-204. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-79063-3_9

Post-quantum security of the sponge construction

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this