Hidden Shift Quantum Cryptanalysis and Implications View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2018-10-27

AUTHORS

Xavier Bonnetain , María Naya-Plasencia

ABSTRACT

At Eurocrypt 2017 a tweak to counter Simon’s quantum attack was proposed: replace the common bitwise addition with other operations, as a modular addition. The starting point of our paper is a follow up of these previous results:First, we have developed new algorithms that improves and generalizes Kuperberg’s algorithm for the hidden shift problem, which is the algorithm that applies instead of Simon when considering modular additions. Thanks to our improved algorithm, we have been able to build a quantum attack in the superposition model on Poly1305, proposed at FSE 2005, widely used and claimed to be quantumly secure. We also answer an open problem by analyzing the effect of the tweak to the FX construction.We have also generalized the algorithm. We propose for the first time a quantum algorithm for solving the hidden problem with parallel modular additions, with a complexity that matches both Simon and Kuperberg in its extremes.In order to verify our theoretical analysis, and to get concrete estimates of the cost of the algorithms, we have simulated them, and were able to validate our estimated complexities.Finally, we analyze the security of some classical symmetric constructions with concrete parameters, to evaluate the impact and practicality of the proposed tweak. We concluded that the tweak does not seem to be efficient. More... »

PAGES

560-592

Book

TITLE

Advances in Cryptology – ASIACRYPT 2018

ISBN

978-3-030-03325-5
978-3-030-03326-2

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-030-03326-2_19

DOI

http://dx.doi.org/10.1007/978-3-030-03326-2_19

DIMENSIONS

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


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": "Inria, Paris, France", 
          "id": "http://www.grid.ac/institutes/grid.5328.c", 
          "name": [
            "Sorbonne Universit\u00e9, Coll\u00e8ge Doctoral, F-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"
      }
    ], 
    "datePublished": "2018-10-27", 
    "datePublishedReg": "2018-10-27", 
    "description": "At Eurocrypt\u00a02017 a tweak to counter Simon\u2019s quantum attack was proposed: replace the common bitwise addition with other operations, as a modular addition. The starting point of our paper is a follow up of these previous results:First, we have developed new algorithms that improves and generalizes Kuperberg\u2019s algorithm for the hidden shift problem, which is the algorithm that applies instead of Simon when considering modular additions. Thanks to our improved algorithm, we have been able to build a quantum attack in the superposition model on Poly1305, proposed at FSE\u00a02005, widely used and claimed to be quantumly secure. We also answer an open problem by analyzing the effect of the tweak to the FX construction.We have also generalized the algorithm. We propose for the first time a quantum algorithm for solving the hidden problem with parallel modular additions, with a complexity that matches both Simon and Kuperberg in its extremes.In order to verify our theoretical analysis, and to get concrete estimates of the cost of the algorithms, we have simulated them, and were able to validate our estimated complexities.Finally, we analyze the security of some classical symmetric constructions with concrete parameters, to evaluate the impact and practicality of the proposed tweak. We concluded that the tweak does not seem to be efficient.", 
    "editor": [
      {
        "familyName": "Peyrin", 
        "givenName": "Thomas", 
        "type": "Person"
      }, 
      {
        "familyName": "Galbraith", 
        "givenName": "Steven", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-030-03326-2_19", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-030-03325-5", 
        "978-3-030-03326-2"
      ], 
      "name": "Advances in Cryptology \u2013 ASIACRYPT 2018", 
      "type": "Book"
    }, 
    "keywords": [
      "quantum attacks", 
      "bitwise addition", 
      "quantum algorithms", 
      "modular addition", 
      "open problem", 
      "concrete estimates", 
      "quantum cryptanalysis", 
      "theoretical analysis", 
      "superposition model", 
      "new algorithm", 
      "algorithm", 
      "concrete parameters", 
      "previous results", 
      "improved algorithm", 
      "problem", 
      "symmetric construction", 
      "FX construction", 
      "complexity", 
      "starting point", 
      "Kuperberg", 
      "shift problem", 
      "parameters", 
      "construction", 
      "estimates", 
      "model", 
      "Simon", 
      "Eurocrypt", 
      "point", 
      "cryptanalysis", 
      "order", 
      "operation", 
      "practicality", 
      "thanks", 
      "first time", 
      "results", 
      "cost", 
      "addition", 
      "analysis", 
      "extremes", 
      "time", 
      "attacks", 
      "Poly1305", 
      "effect", 
      "FSE", 
      "security", 
      "TWEAK", 
      "impact", 
      "implications", 
      "follow", 
      "paper"
    ], 
    "name": "Hidden Shift Quantum Cryptanalysis and Implications", 
    "pagination": "560-592", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1107870546"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-030-03326-2_19"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-030-03326-2_19", 
      "https://app.dimensions.ai/details/publication/pub.1107870546"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-09-02T16:16", 
    "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_430.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-030-03326-2_19"
  }
]
 

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-03326-2_19'

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-03326-2_19'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-03326-2_19'

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-03326-2_19'


 

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

122 TRIPLES      22 PREDICATES      74 URIs      67 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-030-03326-2_19 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N05650fa680b44cb9b526691f253f3ab2
4 schema:datePublished 2018-10-27
5 schema:datePublishedReg 2018-10-27
6 schema:description At Eurocrypt 2017 a tweak to counter Simon’s quantum attack was proposed: replace the common bitwise addition with other operations, as a modular addition. The starting point of our paper is a follow up of these previous results:First, we have developed new algorithms that improves and generalizes Kuperberg’s algorithm for the hidden shift problem, which is the algorithm that applies instead of Simon when considering modular additions. Thanks to our improved algorithm, we have been able to build a quantum attack in the superposition model on Poly1305, proposed at FSE 2005, widely used and claimed to be quantumly secure. We also answer an open problem by analyzing the effect of the tweak to the FX construction.We have also generalized the algorithm. We propose for the first time a quantum algorithm for solving the hidden problem with parallel modular additions, with a complexity that matches both Simon and Kuperberg in its extremes.In order to verify our theoretical analysis, and to get concrete estimates of the cost of the algorithms, we have simulated them, and were able to validate our estimated complexities.Finally, we analyze the security of some classical symmetric constructions with concrete parameters, to evaluate the impact and practicality of the proposed tweak. We concluded that the tweak does not seem to be efficient.
7 schema:editor Nb402a162ec5549019d78419a4b74cd36
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf Nbf7b5423dc784aaebd78943a2229866c
11 schema:keywords Eurocrypt
12 FSE
13 FX construction
14 Kuperberg
15 Poly1305
16 Simon
17 TWEAK
18 addition
19 algorithm
20 analysis
21 attacks
22 bitwise addition
23 complexity
24 concrete estimates
25 concrete parameters
26 construction
27 cost
28 cryptanalysis
29 effect
30 estimates
31 extremes
32 first time
33 follow
34 impact
35 implications
36 improved algorithm
37 model
38 modular addition
39 new algorithm
40 open problem
41 operation
42 order
43 paper
44 parameters
45 point
46 practicality
47 previous results
48 problem
49 quantum algorithms
50 quantum attacks
51 quantum cryptanalysis
52 results
53 security
54 shift problem
55 starting point
56 superposition model
57 symmetric construction
58 thanks
59 theoretical analysis
60 time
61 schema:name Hidden Shift Quantum Cryptanalysis and Implications
62 schema:pagination 560-592
63 schema:productId N18058557916447d39dbf811fe99d740b
64 N63d21caa05a746ab90f99352dc142527
65 schema:publisher N7609bf8f639f4bb6bf6f7469da47f74a
66 schema:sameAs https://app.dimensions.ai/details/publication/pub.1107870546
67 https://doi.org/10.1007/978-3-030-03326-2_19
68 schema:sdDatePublished 2022-09-02T16:16
69 schema:sdLicense https://scigraph.springernature.com/explorer/license/
70 schema:sdPublisher Na5c0e554f6c943c1a55e17fb2890d366
71 schema:url https://doi.org/10.1007/978-3-030-03326-2_19
72 sgo:license sg:explorer/license/
73 sgo:sdDataset chapters
74 rdf:type schema:Chapter
75 N05650fa680b44cb9b526691f253f3ab2 rdf:first sg:person.07625700740.58
76 rdf:rest N3cd39eb93d7b4463903295906bc1f4fc
77 N18058557916447d39dbf811fe99d740b schema:name doi
78 schema:value 10.1007/978-3-030-03326-2_19
79 rdf:type schema:PropertyValue
80 N3cd39eb93d7b4463903295906bc1f4fc rdf:first sg:person.013206304341.94
81 rdf:rest rdf:nil
82 N63d21caa05a746ab90f99352dc142527 schema:name dimensions_id
83 schema:value pub.1107870546
84 rdf:type schema:PropertyValue
85 N7609bf8f639f4bb6bf6f7469da47f74a schema:name Springer Nature
86 rdf:type schema:Organisation
87 N7da4a4e15d8740249c4b191a1675d9d0 rdf:first N9d88f431c78a41aca940ab36c3b2013a
88 rdf:rest rdf:nil
89 N9d88f431c78a41aca940ab36c3b2013a schema:familyName Galbraith
90 schema:givenName Steven
91 rdf:type schema:Person
92 Na5c0e554f6c943c1a55e17fb2890d366 schema:name Springer Nature - SN SciGraph project
93 rdf:type schema:Organization
94 Nb402a162ec5549019d78419a4b74cd36 rdf:first Nc90ea9b35b5c494a89e7c3db26418ff6
95 rdf:rest N7da4a4e15d8740249c4b191a1675d9d0
96 Nbf7b5423dc784aaebd78943a2229866c schema:isbn 978-3-030-03325-5
97 978-3-030-03326-2
98 schema:name Advances in Cryptology – ASIACRYPT 2018
99 rdf:type schema:Book
100 Nc90ea9b35b5c494a89e7c3db26418ff6 schema:familyName Peyrin
101 schema:givenName Thomas
102 rdf:type schema:Person
103 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
104 schema:name Information and Computing Sciences
105 rdf:type schema:DefinedTerm
106 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
107 schema:name Computation Theory and Mathematics
108 rdf:type schema:DefinedTerm
109 sg:person.013206304341.94 schema:affiliation grid-institutes:grid.5328.c
110 schema:familyName Naya-Plasencia
111 schema:givenName María
112 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013206304341.94
113 rdf:type schema:Person
114 sg:person.07625700740.58 schema:affiliation grid-institutes:grid.5328.c
115 schema:familyName Bonnetain
116 schema:givenName Xavier
117 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07625700740.58
118 rdf:type schema:Person
119 grid-institutes:grid.5328.c schema:alternateName Inria, Paris, France
120 schema:name Inria, Paris, France
121 Sorbonne Université, Collège Doctoral, F-75005, Paris, France
122 rdf:type schema:Organization
 




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


...