On Quantum Slide Attacks View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2020-01-10

AUTHORS

Xavier Bonnetain , María Naya-Plasencia , André Schrottenloher

ABSTRACT

At Crypto 2016, Kaplan et al. proposed the first quantum exponential acceleration of a classical symmetric cryptanalysis technique: they showed that, in the superposition query model, Simon’s algorithm could be applied to accelerate the slide attack on the alternate-key cipher. This allows to recover an n-bit key with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathop {}\mathopen {}\mathcal {O}\mathopen {}\left( n\right) $$\end{document} queries.In this paper we propose many other types of quantum slide attacks, inspired by classical techniques including sliding with a twist, complementation slide and mirror slidex. We also propose four-round self-similarity attacks for Feistel ciphers when using XOR operations. Some of these variants combined with whitening keys (FX construction) can also be successfully attacked. We present a surprising new result involving composition of quantum algorithms, that allows to combine some quantum slide attacks with a quantum attack on the round function, allowing an efficient key-recovery even if this function is strong classically.Finally, we analyze the case of quantum slide attacks exploiting cycle-finding, whose possibility was mentioned in a paper by Bar-On et al. in 2015, where these attacks were introduced. We show that the speed-up is smaller than expected and less impressive than the above variants, but nevertheless provide improved complexities on the previous known quantum attacks in the superposition model for some self-similar SPN and Feistel constructions. More... »

PAGES

492-519

Book

TITLE

Selected Areas in Cryptography – SAC 2019

ISBN

978-3-030-38470-8
978-3-030-38471-5

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-030-38471-5_20

DOI

http://dx.doi.org/10.1007/978-3-030-38471-5_20

DIMENSIONS

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


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/02", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Physical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0206", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Quantum Physics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Inria, Paris, France", 
          "id": "http://www.grid.ac/institutes/grid.5328.c", 
          "name": [
            "Coll\u00e8ge Doctoral, Sorbonne Universit\u00e9, 75005, Paris, France", 
            "Inria, Paris, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Bonnetain", 
        "givenName": "Xavier", 
        "id": "sg:person.07625700740.58", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07625700740.58"
        ], 
        "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": "2020-01-10", 
    "datePublishedReg": "2020-01-10", 
    "description": "At Crypto 2016, Kaplan et al. proposed the first quantum exponential acceleration of a classical symmetric cryptanalysis technique: they showed that, in the superposition query model, Simon\u2019s algorithm could be applied to accelerate the slide attack on the alternate-key cipher. This allows to recover an n-bit key with \\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}$$\\mathop {}\\mathopen {}\\mathcal {O}\\mathopen {}\\left( n\\right) $$\\end{document} queries.In this paper we propose many other types of quantum slide attacks, inspired by classical techniques including sliding with a twist, complementation slide and mirror slidex. We also propose four-round self-similarity attacks for Feistel ciphers when using XOR operations. Some of these variants combined with whitening keys (FX construction) can also be successfully attacked. We present a surprising new result involving composition of quantum algorithms, that allows to combine some quantum slide attacks with a quantum attack on the round function, allowing an efficient key-recovery even if this function is strong classically.Finally, we analyze the case of quantum slide attacks exploiting cycle-finding, whose possibility was mentioned in a paper by Bar-On et al. in 2015, where these attacks were introduced. We show that the speed-up is smaller than expected and less impressive than the above variants, but nevertheless provide improved complexities on the previous known quantum attacks in the superposition model for some self-similar SPN and Feistel constructions.", 
    "editor": [
      {
        "familyName": "Paterson", 
        "givenName": "Kenneth G.", 
        "type": "Person"
      }, 
      {
        "familyName": "Stebila", 
        "givenName": "Douglas", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-030-38471-5_20", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-030-38470-8", 
        "978-3-030-38471-5"
      ], 
      "name": "Selected Areas in Cryptography \u2013 SAC 2019", 
      "type": "Book"
    }, 
    "keywords": [
      "surprising new result", 
      "quantum algorithms", 
      "quantum attacks", 
      "Simon\u2019s algorithm", 
      "slide attack", 
      "query model", 
      "superposition model", 
      "XOR operation", 
      "CRYPTO 2016", 
      "et al", 
      "cryptanalysis techniques", 
      "new results", 
      "algorithm", 
      "round function", 
      "attacks", 
      "cipher", 
      "n-bit key", 
      "Feistel construction", 
      "exponential acceleration", 
      "al", 
      "queries", 
      "classical techniques", 
      "Kaplan et al", 
      "acceleration", 
      "key", 
      "Feistel ciphers", 
      "technique", 
      "complexity", 
      "model", 
      "function", 
      "possibility", 
      "twist", 
      "operation", 
      "composition", 
      "bar", 
      "variants", 
      "construction", 
      "results", 
      "SPN", 
      "paper", 
      "slides", 
      "cases", 
      "types", 
      "above variants", 
      "Slidex"
    ], 
    "name": "On Quantum Slide Attacks", 
    "pagination": "492-519", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1123979149"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-030-38471-5_20"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-030-38471-5_20", 
      "https://app.dimensions.ai/details/publication/pub.1123979149"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-12-01T06:46", 
    "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_131.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-030-38471-5_20"
  }
]
 

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-030-38471-5_20'

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-030-38471-5_20'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-38471-5_20'

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-030-38471-5_20'


 

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

124 TRIPLES      22 PREDICATES      69 URIs      62 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-030-38471-5_20 schema:about anzsrc-for:02
2 anzsrc-for:0206
3 schema:author N7bd1d62c30c547be9ff3e5d234c8a759
4 schema:datePublished 2020-01-10
5 schema:datePublishedReg 2020-01-10
6 schema:description At Crypto 2016, Kaplan et al. proposed the first quantum exponential acceleration of a classical symmetric cryptanalysis technique: they showed that, in the superposition query model, Simon’s algorithm could be applied to accelerate the slide attack on the alternate-key cipher. This allows to recover an n-bit key with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathop {}\mathopen {}\mathcal {O}\mathopen {}\left( n\right) $$\end{document} queries.In this paper we propose many other types of quantum slide attacks, inspired by classical techniques including sliding with a twist, complementation slide and mirror slidex. We also propose four-round self-similarity attacks for Feistel ciphers when using XOR operations. Some of these variants combined with whitening keys (FX construction) can also be successfully attacked. We present a surprising new result involving composition of quantum algorithms, that allows to combine some quantum slide attacks with a quantum attack on the round function, allowing an efficient key-recovery even if this function is strong classically.Finally, we analyze the case of quantum slide attacks exploiting cycle-finding, whose possibility was mentioned in a paper by Bar-On et al. in 2015, where these attacks were introduced. We show that the speed-up is smaller than expected and less impressive than the above variants, but nevertheless provide improved complexities on the previous known quantum attacks in the superposition model for some self-similar SPN and Feistel constructions.
7 schema:editor Na6bc782fa2b6408388a51f88ee9ca91d
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf Nb2e1986291c642e3a68982a434b30a94
11 schema:keywords CRYPTO 2016
12 Feistel ciphers
13 Feistel construction
14 Kaplan et al
15 SPN
16 Simon’s algorithm
17 Slidex
18 XOR operation
19 above variants
20 acceleration
21 al
22 algorithm
23 attacks
24 bar
25 cases
26 cipher
27 classical techniques
28 complexity
29 composition
30 construction
31 cryptanalysis techniques
32 et al
33 exponential acceleration
34 function
35 key
36 model
37 n-bit key
38 new results
39 operation
40 paper
41 possibility
42 quantum algorithms
43 quantum attacks
44 queries
45 query model
46 results
47 round function
48 slide attack
49 slides
50 superposition model
51 surprising new result
52 technique
53 twist
54 types
55 variants
56 schema:name On Quantum Slide Attacks
57 schema:pagination 492-519
58 schema:productId Nd9da27da7f6349458e7160731b985b8f
59 Nf497c0235bab46f9a5afc83da687160a
60 schema:publisher N9e5cc47719b947b8bc8d84d92c9fc8d3
61 schema:sameAs https://app.dimensions.ai/details/publication/pub.1123979149
62 https://doi.org/10.1007/978-3-030-38471-5_20
63 schema:sdDatePublished 2022-12-01T06:46
64 schema:sdLicense https://scigraph.springernature.com/explorer/license/
65 schema:sdPublisher N5eb6d4b05b514479a1d417288283b8e6
66 schema:url https://doi.org/10.1007/978-3-030-38471-5_20
67 sgo:license sg:explorer/license/
68 sgo:sdDataset chapters
69 rdf:type schema:Chapter
70 N2ff0c5fbb935416bbc642a8ed859331c rdf:first sg:person.07436415541.40
71 rdf:rest rdf:nil
72 N4e82f62545ba44ae98dd328cba02a8b6 rdf:first sg:person.013206304341.94
73 rdf:rest N2ff0c5fbb935416bbc642a8ed859331c
74 N5eb6d4b05b514479a1d417288283b8e6 schema:name Springer Nature - SN SciGraph project
75 rdf:type schema:Organization
76 N7bd1d62c30c547be9ff3e5d234c8a759 rdf:first sg:person.07625700740.58
77 rdf:rest N4e82f62545ba44ae98dd328cba02a8b6
78 N9708bb9e6b294f27952fc2768ab875e8 schema:familyName Paterson
79 schema:givenName Kenneth G.
80 rdf:type schema:Person
81 N9e5cc47719b947b8bc8d84d92c9fc8d3 schema:name Springer Nature
82 rdf:type schema:Organisation
83 Na6bc782fa2b6408388a51f88ee9ca91d rdf:first N9708bb9e6b294f27952fc2768ab875e8
84 rdf:rest Nc9395b2c37c34b728558f587618865dd
85 Nb2e1986291c642e3a68982a434b30a94 schema:isbn 978-3-030-38470-8
86 978-3-030-38471-5
87 schema:name Selected Areas in Cryptography – SAC 2019
88 rdf:type schema:Book
89 Nc51856c824b34f57a7ae431701833a48 schema:familyName Stebila
90 schema:givenName Douglas
91 rdf:type schema:Person
92 Nc9395b2c37c34b728558f587618865dd rdf:first Nc51856c824b34f57a7ae431701833a48
93 rdf:rest rdf:nil
94 Nd9da27da7f6349458e7160731b985b8f schema:name doi
95 schema:value 10.1007/978-3-030-38471-5_20
96 rdf:type schema:PropertyValue
97 Nf497c0235bab46f9a5afc83da687160a schema:name dimensions_id
98 schema:value pub.1123979149
99 rdf:type schema:PropertyValue
100 anzsrc-for:02 schema:inDefinedTermSet anzsrc-for:
101 schema:name Physical Sciences
102 rdf:type schema:DefinedTerm
103 anzsrc-for:0206 schema:inDefinedTermSet anzsrc-for:
104 schema:name Quantum Physics
105 rdf:type schema:DefinedTerm
106 sg:person.013206304341.94 schema:affiliation grid-institutes:grid.5328.c
107 schema:familyName Naya-Plasencia
108 schema:givenName María
109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013206304341.94
110 rdf:type schema:Person
111 sg:person.07436415541.40 schema:affiliation grid-institutes:grid.5328.c
112 schema:familyName Schrottenloher
113 schema:givenName André
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07436415541.40
115 rdf:type schema:Person
116 sg:person.07625700740.58 schema:affiliation grid-institutes:grid.5328.c
117 schema:familyName Bonnetain
118 schema:givenName Xavier
119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07625700740.58
120 rdf:type schema:Person
121 grid-institutes:grid.5328.c schema:alternateName Inria, Paris, France
122 schema:name Collège Doctoral, Sorbonne Université, 75005, Paris, France
123 Inria, Paris, France
124 rdf:type schema:Organization
 




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


...