Breaking Symmetric Cryptosystems Using Quantum Period Finding View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2016-07-21

AUTHORS

Marc Kaplan , Gaëtan Leurent , Anthony Leverrier , María Naya-Plasencia

ABSTRACT

Due to Shor’s algorithm, quantum computers are a severe threat for public key cryptography. This motivated the cryptographic community to search for quantum-safe solutions. On the other hand, the impact of quantum computing on secret key cryptography is much less understood. In this paper, we consider attacks where an adversary can query an oracle implementing a cryptographic primitive in a quantum superposition of different states. This model gives a lot of power to the adversary, but recent results show that it is nonetheless possible to build secure cryptosystems in it.We study applications of a quantum procedure called Simon’s algorithm (the simplest quantum period finding algorithm) in order to attack symmetric cryptosystems in this model. Following previous works in this direction, we show that several classical attacks based on finding collisions can be dramatically sped up using Simon’s algorithm: finding a collision requires \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varOmega (2^{n/2})$$\end{document} queries in the classical setting, but when collisions happen with some hidden periodicity, they can be found with only O(n) queries in the quantum model.We obtain attacks with very strong implications. First, we show that the most widely used modes of operation for authentication and authenticated encryption (e.g. CBC-MAC, PMAC, GMAC, GCM, and OCB) are completely broken in this security model. Our attacks are also applicable to many CAESAR candidates: CLOC, AEZ, COPA, OTR, POET, OMD, and Minalpher. This is quite surprising compared to the situation with encryption modes: Anand et al. show that standard modes are secure with a quantum-secure PRF.Second, we show that Simon’s algorithm can also be applied to slide attacks, leading to an exponential speed-up of a classical symmetric cryptanalysis technique in the quantum model. More... »

PAGES

207-237

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-662-53008-5_8

DOI

http://dx.doi.org/10.1007/978-3-662-53008-5_8

DIMENSIONS

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


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": "School of Informatics, University of Edinburgh, 10 Crichton Street, EH8 9AB, Edinburgh, UK", 
          "id": "http://www.grid.ac/institutes/grid.4305.2", 
          "name": [
            "LTCI, T\u00e9l\u00e9com ParisTech, 23 avenue d\u2019Italie, 75214, Paris CEDEX 13, France", 
            "School of Informatics, University of Edinburgh, 10 Crichton Street, EH8 9AB, Edinburgh, UK"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kaplan", 
        "givenName": "Marc", 
        "id": "sg:person.013445525307.04", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013445525307.04"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Inria Paris, Paris, France", 
          "id": "http://www.grid.ac/institutes/grid.5328.c", 
          "name": [
            "Inria Paris, 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, Paris, France", 
          "id": "http://www.grid.ac/institutes/grid.5328.c", 
          "name": [
            "Inria Paris, Paris, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Leverrier", 
        "givenName": "Anthony", 
        "id": "sg:person.0761517113.31", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0761517113.31"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Inria Paris, Paris, France", 
          "id": "http://www.grid.ac/institutes/grid.5328.c", 
          "name": [
            "Inria Paris, 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"
      }
    ], 
    "datePublished": "2016-07-21", 
    "datePublishedReg": "2016-07-21", 
    "description": "Due to Shor\u2019s algorithm, quantum computers are a severe threat for public key cryptography. This motivated the cryptographic community to search for quantum-safe solutions. On the other hand, the impact of quantum computing on secret key cryptography is much less understood. In this paper, we consider attacks where an adversary can query an oracle implementing a cryptographic primitive in a quantum superposition of different states. This model gives a lot of power to the adversary, but recent results show that it is nonetheless possible to build secure cryptosystems in it.We study applications of a quantum procedure called Simon\u2019s algorithm (the simplest quantum period finding algorithm) in order to attack symmetric cryptosystems in this model. Following previous works in this direction, we show that several classical attacks based on finding collisions can be dramatically sped up using Simon\u2019s algorithm: finding a collision requires \\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}$$\\varOmega (2^{n/2})$$\\end{document} queries in the classical setting, but when collisions happen with some hidden periodicity, they can be found with only O(n) queries in the quantum model.We obtain attacks with very strong implications. First, we show that the most widely used modes of operation for authentication and authenticated encryption (e.g. CBC-MAC, PMAC, GMAC, GCM, and OCB) are completely broken in this security model. Our attacks are also applicable to many CAESAR candidates: CLOC, AEZ, COPA, OTR, POET, OMD, and Minalpher. This is quite surprising compared to the situation with encryption modes: Anand et al. show that standard modes are secure with a quantum-secure PRF.Second, we show that Simon\u2019s algorithm can also be applied to slide attacks, leading to an exponential speed-up of a classical symmetric cryptanalysis technique in the quantum model.", 
    "editor": [
      {
        "familyName": "Robshaw", 
        "givenName": "Matthew", 
        "type": "Person"
      }, 
      {
        "familyName": "Katz", 
        "givenName": "Jonathan", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-662-53008-5_8", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-662-53007-8", 
        "978-3-662-53008-5"
      ], 
      "name": "Advances in Cryptology \u2013 CRYPTO 2016", 
      "type": "Book"
    }, 
    "keywords": [
      "key cryptography", 
      "Simon\u2019s algorithm", 
      "symmetric cryptosystem", 
      "secret key cryptography", 
      "public key cryptography", 
      "secure cryptosystem", 
      "security model", 
      "cryptographic primitives", 
      "cryptographic community", 
      "CAESAR candidates", 
      "encryption mode", 
      "classical attacks", 
      "Shor\u2019s algorithm", 
      "cryptanalysis techniques", 
      "cryptosystem", 
      "Anand et al", 
      "quantum computer", 
      "algorithm", 
      "queries", 
      "period finding", 
      "cryptography", 
      "adversary", 
      "attacks", 
      "quantum computing", 
      "quantum model", 
      "quantum procedure", 
      "slide attack", 
      "previous work", 
      "classical setting", 
      "encryption", 
      "computing", 
      "authentication", 
      "quantum superposition", 
      "mode of operation", 
      "primitives", 
      "oracle", 
      "computer", 
      "Minalpher", 
      "severe threat", 
      "CLOC", 
      "collisions", 
      "hidden periodicity", 
      "model", 
      "recent results", 
      "different states", 
      "applications", 
      "standard mode", 
      "operation", 
      "threat", 
      "technique", 
      "mode", 
      "AEZ", 
      "solution", 
      "work", 
      "situation", 
      "superposition", 
      "et al", 
      "order", 
      "strong implications", 
      "power", 
      "periodicity", 
      "hand", 
      "community", 
      "state", 
      "results", 
      "direction", 
      "setting", 
      "PRF", 
      "al", 
      "candidates", 
      "procedure", 
      "impact", 
      "CopA", 
      "OTR", 
      "OMD", 
      "implications", 
      "paper", 
      "findings", 
      "poet"
    ], 
    "name": "Breaking Symmetric Cryptosystems Using Quantum Period Finding", 
    "pagination": "207-237", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1041880057"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-662-53008-5_8"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-662-53008-5_8", 
      "https://app.dimensions.ai/details/publication/pub.1041880057"
    ], 
    "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_338.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-662-53008-5_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-662-53008-5_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-662-53008-5_8'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-53008-5_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-662-53008-5_8'


 

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

172 TRIPLES      22 PREDICATES      104 URIs      96 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-662-53008-5_8 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 anzsrc-for:0804
4 schema:author Na00b4553bf57481fa3d135ba65513904
5 schema:datePublished 2016-07-21
6 schema:datePublishedReg 2016-07-21
7 schema:description Due to Shor’s algorithm, quantum computers are a severe threat for public key cryptography. This motivated the cryptographic community to search for quantum-safe solutions. On the other hand, the impact of quantum computing on secret key cryptography is much less understood. In this paper, we consider attacks where an adversary can query an oracle implementing a cryptographic primitive in a quantum superposition of different states. This model gives a lot of power to the adversary, but recent results show that it is nonetheless possible to build secure cryptosystems in it.We study applications of a quantum procedure called Simon’s algorithm (the simplest quantum period finding algorithm) in order to attack symmetric cryptosystems in this model. Following previous works in this direction, we show that several classical attacks based on finding collisions can be dramatically sped up using Simon’s algorithm: finding a collision requires \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varOmega (2^{n/2})$$\end{document} queries in the classical setting, but when collisions happen with some hidden periodicity, they can be found with only O(n) queries in the quantum model.We obtain attacks with very strong implications. First, we show that the most widely used modes of operation for authentication and authenticated encryption (e.g. CBC-MAC, PMAC, GMAC, GCM, and OCB) are completely broken in this security model. Our attacks are also applicable to many CAESAR candidates: CLOC, AEZ, COPA, OTR, POET, OMD, and Minalpher. This is quite surprising compared to the situation with encryption modes: Anand et al. show that standard modes are secure with a quantum-secure PRF.Second, we show that Simon’s algorithm can also be applied to slide attacks, leading to an exponential speed-up of a classical symmetric cryptanalysis technique in the quantum model.
8 schema:editor N3486ff561f9d41bebd9a9f8c4684953e
9 schema:genre chapter
10 schema:isAccessibleForFree true
11 schema:isPartOf N8b0647c9e0b44531bbd7a657c00c6ac1
12 schema:keywords AEZ
13 Anand et al
14 CAESAR candidates
15 CLOC
16 CopA
17 Minalpher
18 OMD
19 OTR
20 PRF
21 Shor’s algorithm
22 Simon’s algorithm
23 adversary
24 al
25 algorithm
26 applications
27 attacks
28 authentication
29 candidates
30 classical attacks
31 classical setting
32 collisions
33 community
34 computer
35 computing
36 cryptanalysis techniques
37 cryptographic community
38 cryptographic primitives
39 cryptography
40 cryptosystem
41 different states
42 direction
43 encryption
44 encryption mode
45 et al
46 findings
47 hand
48 hidden periodicity
49 impact
50 implications
51 key cryptography
52 mode
53 mode of operation
54 model
55 operation
56 oracle
57 order
58 paper
59 period finding
60 periodicity
61 poet
62 power
63 previous work
64 primitives
65 procedure
66 public key cryptography
67 quantum computer
68 quantum computing
69 quantum model
70 quantum procedure
71 quantum superposition
72 queries
73 recent results
74 results
75 secret key cryptography
76 secure cryptosystem
77 security model
78 setting
79 severe threat
80 situation
81 slide attack
82 solution
83 standard mode
84 state
85 strong implications
86 superposition
87 symmetric cryptosystem
88 technique
89 threat
90 work
91 schema:name Breaking Symmetric Cryptosystems Using Quantum Period Finding
92 schema:pagination 207-237
93 schema:productId N13bf7125be1d41358ce9cdf4aec43fad
94 N4c11eb4717fa435fb51725bc42ad230f
95 schema:publisher Ne9e67794ac68450abf71a95c826b10e9
96 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041880057
97 https://doi.org/10.1007/978-3-662-53008-5_8
98 schema:sdDatePublished 2022-10-01T06:57
99 schema:sdLicense https://scigraph.springernature.com/explorer/license/
100 schema:sdPublisher Nb5ebc38a58d241f7aff30f53d8d16270
101 schema:url https://doi.org/10.1007/978-3-662-53008-5_8
102 sgo:license sg:explorer/license/
103 sgo:sdDataset chapters
104 rdf:type schema:Chapter
105 N13bf7125be1d41358ce9cdf4aec43fad schema:name doi
106 schema:value 10.1007/978-3-662-53008-5_8
107 rdf:type schema:PropertyValue
108 N1fbf9f6551d3433d849d38cb0535316f schema:familyName Katz
109 schema:givenName Jonathan
110 rdf:type schema:Person
111 N25e736b77fb04081afd762eefff51400 rdf:first sg:person.0761517113.31
112 rdf:rest N82d6c2a2ae1e46f6a64e2638ae3813b5
113 N3486ff561f9d41bebd9a9f8c4684953e rdf:first N3ceec2c76d6540759e938bd82fb0cd21
114 rdf:rest N590e8e9cf98b41f2a3845cce304d3012
115 N3ceec2c76d6540759e938bd82fb0cd21 schema:familyName Robshaw
116 schema:givenName Matthew
117 rdf:type schema:Person
118 N4c11eb4717fa435fb51725bc42ad230f schema:name dimensions_id
119 schema:value pub.1041880057
120 rdf:type schema:PropertyValue
121 N590e8e9cf98b41f2a3845cce304d3012 rdf:first N1fbf9f6551d3433d849d38cb0535316f
122 rdf:rest rdf:nil
123 N82d6c2a2ae1e46f6a64e2638ae3813b5 rdf:first sg:person.013206304341.94
124 rdf:rest rdf:nil
125 N8b0647c9e0b44531bbd7a657c00c6ac1 schema:isbn 978-3-662-53007-8
126 978-3-662-53008-5
127 schema:name Advances in Cryptology – CRYPTO 2016
128 rdf:type schema:Book
129 Na00b4553bf57481fa3d135ba65513904 rdf:first sg:person.013445525307.04
130 rdf:rest Nd051556e40144eb6bea16f7798223882
131 Nb5ebc38a58d241f7aff30f53d8d16270 schema:name Springer Nature - SN SciGraph project
132 rdf:type schema:Organization
133 Nd051556e40144eb6bea16f7798223882 rdf:first sg:person.016371722741.32
134 rdf:rest N25e736b77fb04081afd762eefff51400
135 Ne9e67794ac68450abf71a95c826b10e9 schema:name Springer Nature
136 rdf:type schema:Organisation
137 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
138 schema:name Information and Computing Sciences
139 rdf:type schema:DefinedTerm
140 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
141 schema:name Computation Theory and Mathematics
142 rdf:type schema:DefinedTerm
143 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
144 schema:name Data Format
145 rdf:type schema:DefinedTerm
146 sg:person.013206304341.94 schema:affiliation grid-institutes:grid.5328.c
147 schema:familyName Naya-Plasencia
148 schema:givenName María
149 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013206304341.94
150 rdf:type schema:Person
151 sg:person.013445525307.04 schema:affiliation grid-institutes:grid.4305.2
152 schema:familyName Kaplan
153 schema:givenName Marc
154 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013445525307.04
155 rdf:type schema:Person
156 sg:person.016371722741.32 schema:affiliation grid-institutes:grid.5328.c
157 schema:familyName Leurent
158 schema:givenName Gaëtan
159 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016371722741.32
160 rdf:type schema:Person
161 sg:person.0761517113.31 schema:affiliation grid-institutes:grid.5328.c
162 schema:familyName Leverrier
163 schema:givenName Anthony
164 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0761517113.31
165 rdf:type schema:Person
166 grid-institutes:grid.4305.2 schema:alternateName School of Informatics, University of Edinburgh, 10 Crichton Street, EH8 9AB, Edinburgh, UK
167 schema:name LTCI, Télécom ParisTech, 23 avenue d’Italie, 75214, Paris CEDEX 13, France
168 School of Informatics, University of Edinburgh, 10 Crichton Street, EH8 9AB, Edinburgh, UK
169 rdf:type schema:Organization
170 grid-institutes:grid.5328.c schema:alternateName Inria Paris, Paris, France
171 schema:name Inria Paris, Paris, France
172 rdf:type schema:Organization
 




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


...