Post-quantum security of the sponge construction

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

4 Citaties (Scopus)

Uittreksel

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.

TaalEngels
TitelPost-Quantum Cryptography - 9th International Conference, PQCrypto 2018, Proceedings
UitgeverijSpringer
Pagina's185-204
Aantal pagina's20
ISBN van geprinte versie9783319790626
DOI's
StatusGepubliceerd - 1 jan 2018
Evenement9th International Conference on Post-Quantum Cryptography (PQCrypto 2018) - Fort Lauderdale, Verenigde Staten van Amerika
Duur: 9 apr 201811 apr 2018
Congresnummer: 9

Publicatie series

NaamLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10786 LNCS
ISSN van geprinte versie0302-9743
ISSN van elektronische versie1611-3349

Congres

Congres9th International Conference on Post-Quantum Cryptography (PQCrypto 2018)
Verkorte titelPQCrypto 2018
LandVerenigde Staten van Amerika
StadFort Lauderdale
Periode9/04/1811/04/18

Vingerafdruk

Collapsing
Collision
Hash functions
Hash Function
Random Permutation
Algorithm Complexity
Quantum Algorithms
Random Function
Strengthening
Arbitrary
Resistance

Trefwoorden

    Citeer dit

    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 (blz. 185-204). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10786 LNCS). Springer. DOI: 10.1007/978-3-319-79063-3_9
    Czajkowski, Jan ; Groot Bruinderink, Leon ; Hülsing, Andreas ; Schaffner, Christian ; Unruh, Dominique. / Post-quantum security of the sponge construction. Post-Quantum Cryptography - 9th International Conference, PQCrypto 2018, Proceedings. Springer, 2018. blz. 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 = "1",
    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",

    }

    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, blz. 185-204, Fort Lauderdale, Verenigde Staten van Amerika, 9/04/18. DOI: 10.1007/978-3-319-79063-3_9

    Post-quantum security of the sponge construction. / Czajkowski, Jan; Groot Bruinderink, Leon; Hülsing, Andreas; Schaffner, Christian; Unruh, Dominique.

    Post-Quantum Cryptography - 9th International Conference, PQCrypto 2018, Proceedings. Springer, 2018. blz. 185-204 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10786 LNCS).

    Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer 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

    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

    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

    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. blz. 185-204. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). Beschikbaar vanaf, DOI: 10.1007/978-3-319-79063-3_9