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-12-01T06:48", 
    "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_190.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 N08e269e9710645c1a89e0ff01deb4cb9
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 Nbace0a6787684cd39a2abfd90c5334a6
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N8daa3369fd904261a0eba5a432bcfaa8
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 Ncbe005616ab04b51b4bf0ae8a7617590
64 Nd3f2b13e31e847b991ce13ebe5083d7b
65 schema:publisher Neeee3557e06c4da5938fde7ec29ae6d4
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-12-01T06:48
69 schema:sdLicense https://scigraph.springernature.com/explorer/license/
70 schema:sdPublisher N0b2ffd4179ad405b821b8087b2ab99f7
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 N08e269e9710645c1a89e0ff01deb4cb9 rdf:first sg:person.07625700740.58
76 rdf:rest N19913cd557784a3284e5e84b123e3eec
77 N0b2ffd4179ad405b821b8087b2ab99f7 schema:name Springer Nature - SN SciGraph project
78 rdf:type schema:Organization
79 N19913cd557784a3284e5e84b123e3eec rdf:first sg:person.013206304341.94
80 rdf:rest rdf:nil
81 N365f1ec75a5745a3a628bd47e8832739 schema:familyName Galbraith
82 schema:givenName Steven
83 rdf:type schema:Person
84 N6f4bf4efc2bc411ca1d323d9f5b7222e rdf:first N365f1ec75a5745a3a628bd47e8832739
85 rdf:rest rdf:nil
86 N8daa3369fd904261a0eba5a432bcfaa8 schema:isbn 978-3-030-03325-5
87 978-3-030-03326-2
88 schema:name Advances in Cryptology – ASIACRYPT 2018
89 rdf:type schema:Book
90 Nbace0a6787684cd39a2abfd90c5334a6 rdf:first Nfe37df0a619c49fe88f08fb323dcccc1
91 rdf:rest N6f4bf4efc2bc411ca1d323d9f5b7222e
92 Ncbe005616ab04b51b4bf0ae8a7617590 schema:name dimensions_id
93 schema:value pub.1107870546
94 rdf:type schema:PropertyValue
95 Nd3f2b13e31e847b991ce13ebe5083d7b schema:name doi
96 schema:value 10.1007/978-3-030-03326-2_19
97 rdf:type schema:PropertyValue
98 Neeee3557e06c4da5938fde7ec29ae6d4 schema:name Springer Nature
99 rdf:type schema:Organisation
100 Nfe37df0a619c49fe88f08fb323dcccc1 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)


...