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-09-02T16:12", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220902/entities/gbq_results/chapter/chapter_21.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 N35279d5921e9451d8f2acfc0dd5d83aa
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 Nda8fea6f21644d4c9923906fa20ccfad
9 schema:genre chapter
10 schema:isAccessibleForFree false
11 schema:isPartOf N423b2bff1574484da7c06c12e72cb862
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 N4bd9c6b6f1cd46de949e3dbe02347c92
107 Nff5f6505d62243edada0cae36c18eec7
108 schema:publisher N699fbf143bed4451ae062af80cb1a1ae
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-09-02T16:12
112 schema:sdLicense https://scigraph.springernature.com/explorer/license/
113 schema:sdPublisher Nf5b33d36c940447a8fce2ea4303fb150
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 N0dce198cdb69425ab999600f196cbfd2 rdf:first sg:person.013206304341.94
119 rdf:rest N11962158a95649e7b583372c16d65e64
120 N11962158a95649e7b583372c16d65e64 rdf:first sg:person.07436415541.40
121 rdf:rest rdf:nil
122 N35279d5921e9451d8f2acfc0dd5d83aa rdf:first sg:person.01223036665.12
123 rdf:rest N0dce198cdb69425ab999600f196cbfd2
124 N423b2bff1574484da7c06c12e72cb862 schema:isbn 978-3-319-70696-2
125 978-3-319-70697-9
126 schema:name Advances in Cryptology – ASIACRYPT 2017
127 rdf:type schema:Book
128 N4bd9c6b6f1cd46de949e3dbe02347c92 schema:name doi
129 schema:value 10.1007/978-3-319-70697-9_8
130 rdf:type schema:PropertyValue
131 N699fbf143bed4451ae062af80cb1a1ae schema:name Springer Nature
132 rdf:type schema:Organisation
133 N86670554706441f1a6d6e64ac477338f schema:familyName Peyrin
134 schema:givenName Thomas
135 rdf:type schema:Person
136 Nb2a6b47418fd403683c9e950ebe7dba0 rdf:first N86670554706441f1a6d6e64ac477338f
137 rdf:rest rdf:nil
138 Nda8fea6f21644d4c9923906fa20ccfad rdf:first Nf0f444aabc1b49fba28ca70d454d2151
139 rdf:rest Nb2a6b47418fd403683c9e950ebe7dba0
140 Nf0f444aabc1b49fba28ca70d454d2151 schema:familyName Takagi
141 schema:givenName Tsuyoshi
142 rdf:type schema:Person
143 Nf5b33d36c940447a8fce2ea4303fb150 schema:name Springer Nature - SN SciGraph project
144 rdf:type schema:Organization
145 Nff5f6505d62243edada0cae36c18eec7 schema:name dimensions_id
146 schema:value pub.1092754932
147 rdf:type schema:PropertyValue
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)


...