Quantum Linearization Attacks View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2021-12-01

AUTHORS

Xavier Bonnetain , Gaëtan Leurent , María Naya-Plasencia , André Schrottenloher

ABSTRACT

Recent works have shown that quantum period-finding can be used to break many popular constructions (some block ciphers such as Even-Mansour, multiple MACs and AEs...) in the superposition query model. So far, all the constructions broken exhibited a strong algebraic structure, which enables to craft a periodic function of a single input block. Recovering the secret period allows to recover a key, distinguish, break the confidentiality or authenticity of these modes.In this paper, we introduce the quantum linearization attack, a new way of using Simon’s algorithm to target MACs in the superposition query model. Specifically, we use inputs of multiple blocks as an interface to a function hiding a linear structure. Recovering this structure allows to perform forgeries.We also present some variants of this attack that use other quantum algorithms, which are much less common in quantum symmetric cryptanalysis: Deutsch’s, Bernstein-Vazirani’s, and Shor’s. To the best of our knowledge, this is the first time these algorithms have been used in quantum forgery or key-recovery attacks.Our attack breaks many parallelizable MACs such as LightMac, PMAC, and numerous variants with (classical) beyond-birthday-bound security (LightMAC+, PMAC+) or using tweakable block ciphers (ZMAC). More generally, it shows that constructing parallelizable quantum-secure PRFs might be a challenging task. More... »

PAGES

422-452

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-030-92062-3_15

DOI

http://dx.doi.org/10.1007/978-3-030-92062-3_15

DIMENSIONS

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


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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Universit\u00e9 de Lorraine, CNRS, Inria, Nancy, France", 
          "id": "http://www.grid.ac/institutes/grid.29172.3f", 
          "name": [
            "Institute for Quantum Computing, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, ON, Canada", 
            "Universit\u00e9 de Lorraine, CNRS, Inria, Nancy, 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": "Leurent", 
        "givenName": "Ga\u00ebtan", 
        "id": "sg:person.016371722741.32", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016371722741.32"
        ], 
        "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": "Cryptology Group, CWI, Amsterdam, The Netherlands", 
          "id": "http://www.grid.ac/institutes/grid.6054.7", 
          "name": [
            "Cryptology Group, CWI, Amsterdam, The Netherlands"
          ], 
          "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": "2021-12-01", 
    "datePublishedReg": "2021-12-01", 
    "description": "Recent works have shown that quantum period-finding can be used to break many popular constructions (some block ciphers such as Even-Mansour, multiple MACs and AEs...) in the superposition query model. So far, all the constructions broken exhibited a strong algebraic structure, which enables to craft a periodic function of a single input block. Recovering the secret period allows to recover a key, distinguish, break the confidentiality or authenticity of these modes.In this paper, we introduce the quantum linearization attack, a new way of using Simon\u2019s algorithm to target MACs in the superposition query model. Specifically, we use inputs of multiple blocks as an interface to a function hiding a linear structure. Recovering this structure allows to perform forgeries.We also present some variants of this attack that use other quantum algorithms, which are much less common in quantum symmetric cryptanalysis: Deutsch\u2019s, Bernstein-Vazirani\u2019s, and Shor\u2019s. To the best of our knowledge, this is the first time these algorithms have been used in quantum forgery or key-recovery attacks.Our attack breaks many parallelizable MACs such as LightMac, PMAC, and numerous variants with (classical) beyond-birthday-bound security (LightMAC+, PMAC+) or using tweakable block ciphers (ZMAC). More generally, it shows that constructing parallelizable quantum-secure PRFs might be a challenging task.", 
    "editor": [
      {
        "familyName": "Tibouchi", 
        "givenName": "Mehdi", 
        "type": "Person"
      }, 
      {
        "familyName": "Wang", 
        "givenName": "Huaxiong", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-030-92062-3_15", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-030-92061-6", 
        "978-3-030-92062-3"
      ], 
      "name": "Advances in Cryptology \u2013 ASIACRYPT 2021", 
      "type": "Book"
    }, 
    "keywords": [
      "query model", 
      "linearization attack", 
      "birthday-bound security", 
      "tweakable block cipher", 
      "symmetric cryptanalysis", 
      "key recovery attack", 
      "challenging task", 
      "block cipher", 
      "Simon\u2019s algorithm", 
      "input block", 
      "quantum algorithms", 
      "strong algebraic structure", 
      "Bernstein-Vazirani", 
      "multiple blocks", 
      "algorithm", 
      "forgery", 
      "attacks", 
      "MAC", 
      "numerous variants", 
      "LightMAC", 
      "new way", 
      "confidentiality", 
      "cipher", 
      "cryptanalysis", 
      "security", 
      "algebraic structure", 
      "task", 
      "recent work", 
      "PMAC", 
      "Shor", 
      "authenticity", 
      "block", 
      "interface", 
      "model", 
      "input", 
      "construction", 
      "linear structure", 
      "way", 
      "work", 
      "knowledge", 
      "variants", 
      "time", 
      "structure", 
      "function", 
      "PRF", 
      "Deutsch", 
      "mode", 
      "first time", 
      "periodic functions", 
      "popular constructions", 
      "period", 
      "paper"
    ], 
    "name": "Quantum Linearization Attacks", 
    "pagination": "422-452", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1143487636"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-030-92062-3_15"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-030-92062-3_15", 
      "https://app.dimensions.ai/details/publication/pub.1143487636"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-10-01T06:57", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/chapter/chapter_347.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-030-92062-3_15"
  }
]
 

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-92062-3_15'

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-92062-3_15'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-92062-3_15'

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-92062-3_15'


 

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

144 TRIPLES      22 PREDICATES      76 URIs      69 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-030-92062-3_15 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Naf152c800ca641478e5fa15b43fcbe43
4 schema:datePublished 2021-12-01
5 schema:datePublishedReg 2021-12-01
6 schema:description Recent works have shown that quantum period-finding can be used to break many popular constructions (some block ciphers such as Even-Mansour, multiple MACs and AEs...) in the superposition query model. So far, all the constructions broken exhibited a strong algebraic structure, which enables to craft a periodic function of a single input block. Recovering the secret period allows to recover a key, distinguish, break the confidentiality or authenticity of these modes.In this paper, we introduce the quantum linearization attack, a new way of using Simon’s algorithm to target MACs in the superposition query model. Specifically, we use inputs of multiple blocks as an interface to a function hiding a linear structure. Recovering this structure allows to perform forgeries.We also present some variants of this attack that use other quantum algorithms, which are much less common in quantum symmetric cryptanalysis: Deutsch’s, Bernstein-Vazirani’s, and Shor’s. To the best of our knowledge, this is the first time these algorithms have been used in quantum forgery or key-recovery attacks.Our attack breaks many parallelizable MACs such as LightMac, PMAC, and numerous variants with (classical) beyond-birthday-bound security (LightMAC+, PMAC+) or using tweakable block ciphers (ZMAC). More generally, it shows that constructing parallelizable quantum-secure PRFs might be a challenging task.
7 schema:editor Naa1567a521504552b06bdbf53898a6c7
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf Ne05d90c184d247aa9d15731ff0349b7a
11 schema:keywords Bernstein-Vazirani
12 Deutsch
13 LightMAC
14 MAC
15 PMAC
16 PRF
17 Shor
18 Simon’s algorithm
19 algebraic structure
20 algorithm
21 attacks
22 authenticity
23 birthday-bound security
24 block
25 block cipher
26 challenging task
27 cipher
28 confidentiality
29 construction
30 cryptanalysis
31 first time
32 forgery
33 function
34 input
35 input block
36 interface
37 key recovery attack
38 knowledge
39 linear structure
40 linearization attack
41 mode
42 model
43 multiple blocks
44 new way
45 numerous variants
46 paper
47 period
48 periodic functions
49 popular constructions
50 quantum algorithms
51 query model
52 recent work
53 security
54 strong algebraic structure
55 structure
56 symmetric cryptanalysis
57 task
58 time
59 tweakable block cipher
60 variants
61 way
62 work
63 schema:name Quantum Linearization Attacks
64 schema:pagination 422-452
65 schema:productId N1a94b76100d8407dbeda360be2f7fe7b
66 N3a96412e355345d693da4bc7b15a1ca8
67 schema:publisher N7c88651a099d4f7eb3ff768c0b932e91
68 schema:sameAs https://app.dimensions.ai/details/publication/pub.1143487636
69 https://doi.org/10.1007/978-3-030-92062-3_15
70 schema:sdDatePublished 2022-10-01T06:57
71 schema:sdLicense https://scigraph.springernature.com/explorer/license/
72 schema:sdPublisher N6723e857cea547deabc6063de24a6318
73 schema:url https://doi.org/10.1007/978-3-030-92062-3_15
74 sgo:license sg:explorer/license/
75 sgo:sdDataset chapters
76 rdf:type schema:Chapter
77 N16dee1167ad64cbcbf8754bd3cd73c94 rdf:first N216b4956c4b743ba886e13c6da164d54
78 rdf:rest rdf:nil
79 N1959c0055e3c4db18ffd107161318ab0 schema:familyName Tibouchi
80 schema:givenName Mehdi
81 rdf:type schema:Person
82 N1a94b76100d8407dbeda360be2f7fe7b schema:name dimensions_id
83 schema:value pub.1143487636
84 rdf:type schema:PropertyValue
85 N216b4956c4b743ba886e13c6da164d54 schema:familyName Wang
86 schema:givenName Huaxiong
87 rdf:type schema:Person
88 N287cad3d26464c428800832f6e2bfe95 rdf:first sg:person.016371722741.32
89 rdf:rest N50163965e3c24411bcfe41f531ecbc76
90 N3a96412e355345d693da4bc7b15a1ca8 schema:name doi
91 schema:value 10.1007/978-3-030-92062-3_15
92 rdf:type schema:PropertyValue
93 N50163965e3c24411bcfe41f531ecbc76 rdf:first sg:person.013206304341.94
94 rdf:rest Ndcc080f5d1d9489c94ded119fd483d61
95 N6723e857cea547deabc6063de24a6318 schema:name Springer Nature - SN SciGraph project
96 rdf:type schema:Organization
97 N7c88651a099d4f7eb3ff768c0b932e91 schema:name Springer Nature
98 rdf:type schema:Organisation
99 Naa1567a521504552b06bdbf53898a6c7 rdf:first N1959c0055e3c4db18ffd107161318ab0
100 rdf:rest N16dee1167ad64cbcbf8754bd3cd73c94
101 Naf152c800ca641478e5fa15b43fcbe43 rdf:first sg:person.07625700740.58
102 rdf:rest N287cad3d26464c428800832f6e2bfe95
103 Ndcc080f5d1d9489c94ded119fd483d61 rdf:first sg:person.07436415541.40
104 rdf:rest rdf:nil
105 Ne05d90c184d247aa9d15731ff0349b7a schema:isbn 978-3-030-92061-6
106 978-3-030-92062-3
107 schema:name Advances in Cryptology – ASIACRYPT 2021
108 rdf:type schema:Book
109 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
110 schema:name Information and Computing Sciences
111 rdf:type schema:DefinedTerm
112 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
113 schema:name Computation Theory and Mathematics
114 rdf:type schema:DefinedTerm
115 sg:person.013206304341.94 schema:affiliation grid-institutes:grid.5328.c
116 schema:familyName Naya-Plasencia
117 schema:givenName María
118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013206304341.94
119 rdf:type schema:Person
120 sg:person.016371722741.32 schema:affiliation grid-institutes:grid.5328.c
121 schema:familyName Leurent
122 schema:givenName Gaëtan
123 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016371722741.32
124 rdf:type schema:Person
125 sg:person.07436415541.40 schema:affiliation grid-institutes:grid.6054.7
126 schema:familyName Schrottenloher
127 schema:givenName André
128 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07436415541.40
129 rdf:type schema:Person
130 sg:person.07625700740.58 schema:affiliation grid-institutes:grid.29172.3f
131 schema:familyName Bonnetain
132 schema:givenName Xavier
133 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07625700740.58
134 rdf:type schema:Person
135 grid-institutes:grid.29172.3f schema:alternateName Université de Lorraine, CNRS, Inria, Nancy, France
136 schema:name Institute for Quantum Computing, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, ON, Canada
137 Université de Lorraine, CNRS, Inria, Nancy, France
138 rdf:type schema:Organization
139 grid-institutes:grid.5328.c schema:alternateName Inria, Paris, France
140 schema:name Inria, Paris, France
141 rdf:type schema:Organization
142 grid-institutes:grid.6054.7 schema:alternateName Cryptology Group, CWI, Amsterdam, The Netherlands
143 schema:name Cryptology Group, CWI, Amsterdam, The Netherlands
144 rdf:type schema:Organization
 




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


...