An Efficient Quantum Collision Search Algorithm and Implications on Symmetric Cryptography View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2017-11-18

AUTHORS

André Chailloux , María Naya-Plasencia , André Schrottenloher

ABSTRACT

The cryptographic community has widely acknowledged that the emergence of large quantum computers will pose a threat to most current public-key cryptography. Primitives that rely on order-finding problems, such as factoring and computing Discrete Logarithms, can be broken by Shor’s algorithm ([49]).Symmetric primitives, at first sight, seem less impacted by the arrival of quantum computers: Grover’s algorithm [31] for searching in an unstructured database finds a marked element among 2n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{n}$$\end{document} in time O~(2n/2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\widetilde{O}(2^{n / 2})$$\end{document}, providing a quadratic speedup compared to the classical exhaustive search, essentially optimal. Cryptographers then commonly consider that doubling the length of the keys used will be enough to maintain the same level of security.From similar techniques, quantum collision search is known to attain O~(2n/3)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\widetilde{O}(2^{n / 3})$$\end{document}query complexity [20], compared to the classical O(2n/2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(2^{n / 2})$$\end{document}. However this quantum speedup is illusory: the actual quantum computation performed is actually more expensive than in the classical algorithm.In this paper, we investigate quantum collision and multi-target preimage search and present a new algorithm, that uses the amplitude amplification technique. As such, it relies on the same principle as Grover’s search. Our algorithm is the first to propose a time complexity that improves upon O(2n/2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(2^{n/2})$$\end{document}, in a simple setting with a single processor. This time complexity is O~(22n/5)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\widetilde{O}(2^{2n/5})$$\end{document} (equal to its query complexity), with a polynomial quantum memory needed (O(n)), and a small classical memory complexity of O~(2n/5)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\widetilde{O}(2^{n/5})$$\end{document}. For multi-target preimage attacks, these complexities become O~(23n/7)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\widetilde{O}(2^{3n/7})$$\end{document}, O(n) and O~(2n/7)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\widetilde{O}(2^{n/7})$$\end{document} respectively. To the best of our knowledge, this is the first proof of an actual quantum time speedup for collision search. We also propose a parallelization of these algorithms. This result has an impact on several symmetric cryptography scenarios: we detail how to improve upon previous attacks for hash function collisions and multi-target preimages, how to perform an improved key recovery in the multi-user setting, how to improve the collision attacks on operation modes, and point out that these improved algorithms can serve as basic tools for some families of cryptanalytic techniques.In the end, we discuss the implications of these new attacks on post-quantum security. More... »

PAGES

211-240

Book

TITLE

Advances in Cryptology – ASIACRYPT 2017

ISBN

978-3-319-70696-2
978-3-319-70697-9

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-70697-9_8

DOI

http://dx.doi.org/10.1007/978-3-319-70697-9_8

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1092754932


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0804", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Data Format", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Inria, Paris, France", 
          "id": "http://www.grid.ac/institutes/grid.5328.c", 
          "name": [
            "Inria, Paris, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chailloux", 
        "givenName": "Andr\u00e9", 
        "id": "sg:person.01223036665.12", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01223036665.12"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Inria, Paris, France", 
          "id": "http://www.grid.ac/institutes/grid.5328.c", 
          "name": [
            "Inria, Paris, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Naya-Plasencia", 
        "givenName": "Mar\u00eda", 
        "id": "sg:person.013206304341.94", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013206304341.94"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Inria, Paris, France", 
          "id": "http://www.grid.ac/institutes/grid.5328.c", 
          "name": [
            "Inria, Paris, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Schrottenloher", 
        "givenName": "Andr\u00e9", 
        "id": "sg:person.07436415541.40", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07436415541.40"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2017-11-18", 
    "datePublishedReg": "2017-11-18", 
    "description": "The cryptographic community has widely acknowledged that the emergence of large quantum computers will pose a threat to most current public-key cryptography. Primitives that rely on order-finding problems, such as factoring and computing Discrete Logarithms, can be broken by Shor\u2019s algorithm ([49]).Symmetric primitives, at first sight, seem less impacted by the arrival of quantum computers: Grover\u2019s algorithm\u00a0[31] for searching in an unstructured database finds a marked element among 2n\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$2^{n}$$\\end{document} in time O~(2n/2)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\widetilde{O}(2^{n / 2})$$\\end{document}, providing a quadratic speedup compared to the classical exhaustive search, essentially optimal. Cryptographers then commonly consider that doubling the length of the keys used will be enough to maintain the same level of security.From similar techniques, quantum collision search is known to attain O~(2n/3)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\widetilde{O}(2^{n / 3})$$\\end{document}query complexity\u00a0[20], compared to the classical O(2n/2)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$O(2^{n / 2})$$\\end{document}. However this quantum speedup is illusory: the actual quantum computation performed is actually more expensive than in the classical algorithm.In this paper, we investigate quantum collision and multi-target preimage search and present a new algorithm, that uses the amplitude amplification technique. As such, it relies on the same principle as Grover\u2019s search. Our algorithm is the first to propose a time complexity that improves upon O(2n/2)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$O(2^{n/2})$$\\end{document}, in a simple setting with a single processor. This time complexity is O~(22n/5)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\widetilde{O}(2^{2n/5})$$\\end{document} (equal to its query complexity), with a polynomial quantum memory needed (O(n)), and a small classical memory complexity of O~(2n/5)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\widetilde{O}(2^{n/5})$$\\end{document}. For multi-target preimage attacks, these complexities become O~(23n/7)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\widetilde{O}(2^{3n/7})$$\\end{document}, O(n) and O~(2n/7)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\widetilde{O}(2^{n/7})$$\\end{document} respectively. To the best of our knowledge, this is the first proof of an actual quantum time speedup for collision search. We also propose a parallelization of these algorithms. This result has an impact on several symmetric cryptography scenarios: we detail how to improve upon previous attacks for hash function collisions and multi-target preimages, how to perform an improved key recovery in the multi-user setting, how to improve the collision attacks on operation modes, and point out that these improved algorithms can serve as basic tools for some families of cryptanalytic techniques.In the end, we discuss the implications of these new attacks on post-quantum security.", 
    "editor": [
      {
        "familyName": "Takagi", 
        "givenName": "Tsuyoshi", 
        "type": "Person"
      }, 
      {
        "familyName": "Peyrin", 
        "givenName": "Thomas", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-70697-9_8", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-319-70696-2", 
        "978-3-319-70697-9"
      ], 
      "name": "Advances in Cryptology \u2013 ASIACRYPT 2017", 
      "type": "Book"
    }, 
    "keywords": [
      "collision search", 
      "time complexity", 
      "public key cryptography", 
      "multi-user setting", 
      "quantum computer", 
      "amplitude amplification technique", 
      "post-quantum security", 
      "large quantum computer", 
      "unstructured database", 
      "symmetric cryptography", 
      "cryptographic community", 
      "discrete logarithm", 
      "new attacks", 
      "single processor", 
      "time speedup", 
      "memory complexity", 
      "symmetric primitives", 
      "search algorithm", 
      "key recovery", 
      "Shor\u2019s algorithm", 
      "quadratic speedup", 
      "classical algorithms", 
      "Grover search", 
      "exhaustive search", 
      "Grover\u2019s algorithm", 
      "speedup", 
      "improved algorithm", 
      "algorithm", 
      "new algorithm", 
      "cryptanalytic techniques", 
      "collision attack", 
      "cryptography", 
      "quantum speedup", 
      "primitives", 
      "preimage attack", 
      "attacks", 
      "previous attacks", 
      "computer", 
      "complexity", 
      "security", 
      "quantum computation", 
      "simple setting", 
      "classical exhaustive search", 
      "search", 
      "marked element", 
      "basic tool", 
      "similar techniques", 
      "parallelization", 
      "cryptographers", 
      "processors", 
      "first proof", 
      "computation", 
      "technique", 
      "operation mode", 
      "scenarios", 
      "factoring", 
      "database", 
      "key", 
      "same principles", 
      "tool", 
      "memory", 
      "proof", 
      "threat", 
      "same level", 
      "preimage", 
      "knowledge", 
      "collisions", 
      "setting", 
      "quantum collisions", 
      "sight", 
      "first sight", 
      "principles", 
      "arrival", 
      "time", 
      "end", 
      "community", 
      "results", 
      "emergence", 
      "elements", 
      "quantum memory", 
      "mode", 
      "impact", 
      "logarithm", 
      "levels", 
      "implications", 
      "length", 
      "recovery", 
      "illusory", 
      "amplification techniques", 
      "family", 
      "paper", 
      "problem"
    ], 
    "name": "An Efficient Quantum Collision Search Algorithm and Implications on Symmetric Cryptography", 
    "pagination": "211-240", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1092754932"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-70697-9_8"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-70697-9_8", 
      "https://app.dimensions.ai/details/publication/pub.1092754932"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-12-01T06:53", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221201/entities/gbq_results/chapter/chapter_417.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-70697-9_8"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-70697-9_8'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-70697-9_8'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-70697-9_8'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-70697-9_8'


 

This table displays all metadata directly associated to this object as RDF triples.

174 TRIPLES      22 PREDICATES      117 URIs      109 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-70697-9_8 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 anzsrc-for:0804
4 schema:author N52afef3f174d4537a8e5ea082c40f9be
5 schema:datePublished 2017-11-18
6 schema:datePublishedReg 2017-11-18
7 schema:description The cryptographic community has widely acknowledged that the emergence of large quantum computers will pose a threat to most current public-key cryptography. Primitives that rely on order-finding problems, such as factoring and computing Discrete Logarithms, can be broken by Shor’s algorithm ([49]).Symmetric primitives, at first sight, seem less impacted by the arrival of quantum computers: Grover’s algorithm [31] for searching in an unstructured database finds a marked element among 2n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{n}$$\end{document} in time O~(2n/2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\widetilde{O}(2^{n / 2})$$\end{document}, providing a quadratic speedup compared to the classical exhaustive search, essentially optimal. Cryptographers then commonly consider that doubling the length of the keys used will be enough to maintain the same level of security.From similar techniques, quantum collision search is known to attain O~(2n/3)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\widetilde{O}(2^{n / 3})$$\end{document}query complexity [20], compared to the classical O(2n/2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(2^{n / 2})$$\end{document}. However this quantum speedup is illusory: the actual quantum computation performed is actually more expensive than in the classical algorithm.In this paper, we investigate quantum collision and multi-target preimage search and present a new algorithm, that uses the amplitude amplification technique. As such, it relies on the same principle as Grover’s search. Our algorithm is the first to propose a time complexity that improves upon O(2n/2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(2^{n/2})$$\end{document}, in a simple setting with a single processor. This time complexity is O~(22n/5)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\widetilde{O}(2^{2n/5})$$\end{document} (equal to its query complexity), with a polynomial quantum memory needed (O(n)), and a small classical memory complexity of O~(2n/5)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\widetilde{O}(2^{n/5})$$\end{document}. For multi-target preimage attacks, these complexities become O~(23n/7)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\widetilde{O}(2^{3n/7})$$\end{document}, O(n) and O~(2n/7)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\widetilde{O}(2^{n/7})$$\end{document} respectively. To the best of our knowledge, this is the first proof of an actual quantum time speedup for collision search. We also propose a parallelization of these algorithms. This result has an impact on several symmetric cryptography scenarios: we detail how to improve upon previous attacks for hash function collisions and multi-target preimages, how to perform an improved key recovery in the multi-user setting, how to improve the collision attacks on operation modes, and point out that these improved algorithms can serve as basic tools for some families of cryptanalytic techniques.In the end, we discuss the implications of these new attacks on post-quantum security.
8 schema:editor Nf12208ff83794becb3a143cc44066e9d
9 schema:genre chapter
10 schema:isAccessibleForFree false
11 schema:isPartOf N41cdd707527e4c3ca44d811069f345e9
12 schema:keywords Grover search
13 Grover’s algorithm
14 Shor’s algorithm
15 algorithm
16 amplification techniques
17 amplitude amplification technique
18 arrival
19 attacks
20 basic tool
21 classical algorithms
22 classical exhaustive search
23 collision attack
24 collision search
25 collisions
26 community
27 complexity
28 computation
29 computer
30 cryptanalytic techniques
31 cryptographers
32 cryptographic community
33 cryptography
34 database
35 discrete logarithm
36 elements
37 emergence
38 end
39 exhaustive search
40 factoring
41 family
42 first proof
43 first sight
44 illusory
45 impact
46 implications
47 improved algorithm
48 key
49 key recovery
50 knowledge
51 large quantum computer
52 length
53 levels
54 logarithm
55 marked element
56 memory
57 memory complexity
58 mode
59 multi-user setting
60 new algorithm
61 new attacks
62 operation mode
63 paper
64 parallelization
65 post-quantum security
66 preimage
67 preimage attack
68 previous attacks
69 primitives
70 principles
71 problem
72 processors
73 proof
74 public key cryptography
75 quadratic speedup
76 quantum collisions
77 quantum computation
78 quantum computer
79 quantum memory
80 quantum speedup
81 recovery
82 results
83 same level
84 same principles
85 scenarios
86 search
87 search algorithm
88 security
89 setting
90 sight
91 similar techniques
92 simple setting
93 single processor
94 speedup
95 symmetric cryptography
96 symmetric primitives
97 technique
98 threat
99 time
100 time complexity
101 time speedup
102 tool
103 unstructured database
104 schema:name An Efficient Quantum Collision Search Algorithm and Implications on Symmetric Cryptography
105 schema:pagination 211-240
106 schema:productId N945d7662db0a4bcda254ba65d2ea4086
107 Nbde7e1ec82cc4447952e1dae34ef5154
108 schema:publisher N5bafce3cd56a49a49820b3746d0a299d
109 schema:sameAs https://app.dimensions.ai/details/publication/pub.1092754932
110 https://doi.org/10.1007/978-3-319-70697-9_8
111 schema:sdDatePublished 2022-12-01T06:53
112 schema:sdLicense https://scigraph.springernature.com/explorer/license/
113 schema:sdPublisher Ncbc763e2f89b4011ab8143df14ac5b0e
114 schema:url https://doi.org/10.1007/978-3-319-70697-9_8
115 sgo:license sg:explorer/license/
116 sgo:sdDataset chapters
117 rdf:type schema:Chapter
118 N24d07c82721f463e98bd727fceef301d schema:familyName Takagi
119 schema:givenName Tsuyoshi
120 rdf:type schema:Person
121 N279a6e878cfe48e59c843bc7ad60628c rdf:first sg:person.013206304341.94
122 rdf:rest N393a819ad30841efbc48ca84147c289b
123 N393a819ad30841efbc48ca84147c289b rdf:first sg:person.07436415541.40
124 rdf:rest rdf:nil
125 N41cdd707527e4c3ca44d811069f345e9 schema:isbn 978-3-319-70696-2
126 978-3-319-70697-9
127 schema:name Advances in Cryptology – ASIACRYPT 2017
128 rdf:type schema:Book
129 N52afef3f174d4537a8e5ea082c40f9be rdf:first sg:person.01223036665.12
130 rdf:rest N279a6e878cfe48e59c843bc7ad60628c
131 N5bafce3cd56a49a49820b3746d0a299d schema:name Springer Nature
132 rdf:type schema:Organisation
133 N945d7662db0a4bcda254ba65d2ea4086 schema:name doi
134 schema:value 10.1007/978-3-319-70697-9_8
135 rdf:type schema:PropertyValue
136 Nbde7e1ec82cc4447952e1dae34ef5154 schema:name dimensions_id
137 schema:value pub.1092754932
138 rdf:type schema:PropertyValue
139 Ncabda669edd3498fa8d8cda293354058 rdf:first Nd6fdb76559e742088bea2d0ddef20c14
140 rdf:rest rdf:nil
141 Ncbc763e2f89b4011ab8143df14ac5b0e schema:name Springer Nature - SN SciGraph project
142 rdf:type schema:Organization
143 Nd6fdb76559e742088bea2d0ddef20c14 schema:familyName Peyrin
144 schema:givenName Thomas
145 rdf:type schema:Person
146 Nf12208ff83794becb3a143cc44066e9d rdf:first N24d07c82721f463e98bd727fceef301d
147 rdf:rest Ncabda669edd3498fa8d8cda293354058
148 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
149 schema:name Information and Computing Sciences
150 rdf:type schema:DefinedTerm
151 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
152 schema:name Computation Theory and Mathematics
153 rdf:type schema:DefinedTerm
154 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
155 schema:name Data Format
156 rdf:type schema:DefinedTerm
157 sg:person.01223036665.12 schema:affiliation grid-institutes:grid.5328.c
158 schema:familyName Chailloux
159 schema:givenName André
160 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01223036665.12
161 rdf:type schema:Person
162 sg:person.013206304341.94 schema:affiliation grid-institutes:grid.5328.c
163 schema:familyName Naya-Plasencia
164 schema:givenName María
165 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013206304341.94
166 rdf:type schema:Person
167 sg:person.07436415541.40 schema:affiliation grid-institutes:grid.5328.c
168 schema:familyName Schrottenloher
169 schema:givenName André
170 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07436415541.40
171 rdf:type schema:Person
172 grid-institutes:grid.5328.c schema:alternateName Inria, Paris, France
173 schema:name Inria, Paris, France
174 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...