Quantum Algorithms for the -xor Problem View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2018-10-27

AUTHORS

Lorenzo Grassi , María Naya-Plasencia , André Schrottenloher

ABSTRACT

The \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}-xor (or generalized birthday) problem is a widely studied question with many applications in cryptography. It aims at finding k elements of n bits, drawn at random, such that the xor of all of them is 0. The algorithms proposed by Wagner more than fifteen years ago remain the best known classical algorithms for solving them, when disregarding logarithmic factors.In this paper we study these problems in the quantum setting, when considering that the elements are created by querying a random function (or k random functions) \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$H~: \{0,1\}^n \rightarrow \{0,1\}^n$$\end{document}. We consider two scenarios: in one we are able to use a limited amount of quantum memory (i.e. a number O(n) of qubits, the same as the one needed by Grover’s search algorithm), and in the other we consider that the algorithm can use an exponential amount of qubits. Our newly proposed algorithms are of general interest. In both settings, they provide the best known quantum time complexities.In particular, we are able to considerately improve the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$3$$\end{document}-xor algorithm: with limited qubits, we reach a complexity considerably better than what is currently possible for quantum collision search. Furthermore, when having access to exponential amounts of quantum memory, we can take this complexity below \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(2^{n/3})$$\end{document}, the well-known lower bound of quantum collision search, clearly improving the best known quantum time complexity also in this setting.We illustrate the importance of these results with some cryptographic applications. More... »

PAGES

527-559

Book

TITLE

Advances in Cryptology – ASIACRYPT 2018

ISBN

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

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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": "IAIK, Graz University of Technology, Graz, Austria", 
          "id": "http://www.grid.ac/institutes/grid.410413.3", 
          "name": [
            "IAIK, Graz University of Technology, Graz, Austria"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Grassi", 
        "givenName": "Lorenzo", 
        "id": "sg:person.016404105241.53", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016404105241.53"
        ], 
        "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": "2018-10-27", 
    "datePublishedReg": "2018-10-27", 
    "description": "The \\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}$$k$$\\end{document}-xor (or generalized birthday) problem is a widely studied question with many applications in cryptography. It aims at finding k elements of n bits, drawn at random, such that the xor of all of them is 0. The algorithms proposed by Wagner more than fifteen years ago remain the best known classical algorithms for solving them, when disregarding logarithmic factors.In this paper we study these problems in the quantum setting, when considering that the elements are created by querying a random function (or k random functions) \\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}$$H~: \\{0,1\\}^n \\rightarrow \\{0,1\\}^n$$\\end{document}. We consider two scenarios: in one we are able to use a limited amount of quantum memory (i.e. a number O(n) of qubits, the same as the one needed by Grover\u2019s search algorithm), and in the other we consider that the algorithm can use an exponential amount of qubits. Our newly proposed algorithms are of general interest. In both settings, they provide the best known quantum time complexities.In particular, we are able to considerately improve the \\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}$$3$$\\end{document}-xor algorithm: with limited qubits, we reach a complexity considerably better than what is currently possible for quantum collision search. Furthermore, when having access to exponential amounts of quantum memory, we can take this complexity below \\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}$$O(2^{n/3})$$\\end{document}, the well-known lower bound of quantum collision search, clearly improving the best known quantum time complexity also in this setting.We illustrate the importance of these results with some cryptographic applications.", 
    "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_18", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-030-03325-5", 
        "978-3-030-03326-2"
      ], 
      "name": "Advances in Cryptology \u2013 ASIACRYPT 2018", 
      "type": "Book"
    }, 
    "keywords": [
      "collision search", 
      "time complexity", 
      "XOR problem", 
      "exponential amount", 
      "XOR algorithm", 
      "cryptographic applications", 
      "classical algorithms", 
      "quantum algorithms", 
      "algorithm", 
      "quantum setting", 
      "n bits", 
      "complexity", 
      "logarithmic factor", 
      "cryptography", 
      "limited amount", 
      "search", 
      "k elements", 
      "XOR", 
      "applications", 
      "random function", 
      "memory", 
      "bits", 
      "scenarios", 
      "access", 
      "amount", 
      "general interest", 
      "setting", 
      "elements", 
      "quantum memory", 
      "interest", 
      "qubits", 
      "results", 
      "function", 
      "questions", 
      "importance", 
      "problem", 
      "Wagner", 
      "years", 
      "studied question", 
      "factors", 
      "paper"
    ], 
    "name": "Quantum Algorithms for the -xor Problem", 
    "pagination": "527-559", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1107870545"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-030-03326-2_18"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-030-03326-2_18", 
      "https://app.dimensions.ai/details/publication/pub.1107870545"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-10-01T06:52", 
    "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_115.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-030-03326-2_18"
  }
]
 

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_18'

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_18'

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_18'

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_18'


 

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

122 TRIPLES      22 PREDICATES      65 URIs      58 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-030-03326-2_18 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nd62ea719b43044cc9dd0c2390e792f45
4 schema:datePublished 2018-10-27
5 schema:datePublishedReg 2018-10-27
6 schema:description The \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}-xor (or generalized birthday) problem is a widely studied question with many applications in cryptography. It aims at finding k elements of n bits, drawn at random, such that the xor of all of them is 0. The algorithms proposed by Wagner more than fifteen years ago remain the best known classical algorithms for solving them, when disregarding logarithmic factors.In this paper we study these problems in the quantum setting, when considering that the elements are created by querying a random function (or k random functions) \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$H~: \{0,1\}^n \rightarrow \{0,1\}^n$$\end{document}. We consider two scenarios: in one we are able to use a limited amount of quantum memory (i.e. a number O(n) of qubits, the same as the one needed by Grover’s search algorithm), and in the other we consider that the algorithm can use an exponential amount of qubits. Our newly proposed algorithms are of general interest. In both settings, they provide the best known quantum time complexities.In particular, we are able to considerately improve the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$3$$\end{document}-xor algorithm: with limited qubits, we reach a complexity considerably better than what is currently possible for quantum collision search. Furthermore, when having access to exponential amounts of quantum memory, we can take this complexity below \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(2^{n/3})$$\end{document}, the well-known lower bound of quantum collision search, clearly improving the best known quantum time complexity also in this setting.We illustrate the importance of these results with some cryptographic applications.
7 schema:editor N8526e608f5d245fb9b6840c95ba2ca21
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N8336071cfe4c4cee817b2d10729a108f
11 schema:keywords Wagner
12 XOR
13 XOR algorithm
14 XOR problem
15 access
16 algorithm
17 amount
18 applications
19 bits
20 classical algorithms
21 collision search
22 complexity
23 cryptographic applications
24 cryptography
25 elements
26 exponential amount
27 factors
28 function
29 general interest
30 importance
31 interest
32 k elements
33 limited amount
34 logarithmic factor
35 memory
36 n bits
37 paper
38 problem
39 quantum algorithms
40 quantum memory
41 quantum setting
42 qubits
43 questions
44 random function
45 results
46 scenarios
47 search
48 setting
49 studied question
50 time complexity
51 years
52 schema:name Quantum Algorithms for the -xor Problem
53 schema:pagination 527-559
54 schema:productId N6f96d115be514fb0b8e963ee36dcbfbc
55 N7ccb687196db44fe8786340b9ea98d88
56 schema:publisher Ncde364d5a87a4a65b1d96c6886545478
57 schema:sameAs https://app.dimensions.ai/details/publication/pub.1107870545
58 https://doi.org/10.1007/978-3-030-03326-2_18
59 schema:sdDatePublished 2022-10-01T06:52
60 schema:sdLicense https://scigraph.springernature.com/explorer/license/
61 schema:sdPublisher N8a6e38b1fe714f4c8569914159cd6c54
62 schema:url https://doi.org/10.1007/978-3-030-03326-2_18
63 sgo:license sg:explorer/license/
64 sgo:sdDataset chapters
65 rdf:type schema:Chapter
66 N0878cfcd1a724d29a0ce223bc78f7025 schema:familyName Galbraith
67 schema:givenName Steven
68 rdf:type schema:Person
69 N3ab337482c65456f90fda89a85f77ccc rdf:first sg:person.013206304341.94
70 rdf:rest Nd1dd1db7c61242a59164ee92d65f566d
71 N480ca17a53a14f5c8d8a6c0d28faa6cd schema:familyName Peyrin
72 schema:givenName Thomas
73 rdf:type schema:Person
74 N6f96d115be514fb0b8e963ee36dcbfbc schema:name dimensions_id
75 schema:value pub.1107870545
76 rdf:type schema:PropertyValue
77 N7ccb687196db44fe8786340b9ea98d88 schema:name doi
78 schema:value 10.1007/978-3-030-03326-2_18
79 rdf:type schema:PropertyValue
80 N8336071cfe4c4cee817b2d10729a108f schema:isbn 978-3-030-03325-5
81 978-3-030-03326-2
82 schema:name Advances in Cryptology – ASIACRYPT 2018
83 rdf:type schema:Book
84 N8526e608f5d245fb9b6840c95ba2ca21 rdf:first N480ca17a53a14f5c8d8a6c0d28faa6cd
85 rdf:rest N9405878dad7947fb864ca1a4313303cb
86 N8a6e38b1fe714f4c8569914159cd6c54 schema:name Springer Nature - SN SciGraph project
87 rdf:type schema:Organization
88 N9405878dad7947fb864ca1a4313303cb rdf:first N0878cfcd1a724d29a0ce223bc78f7025
89 rdf:rest rdf:nil
90 Ncde364d5a87a4a65b1d96c6886545478 schema:name Springer Nature
91 rdf:type schema:Organisation
92 Nd1dd1db7c61242a59164ee92d65f566d rdf:first sg:person.07436415541.40
93 rdf:rest rdf:nil
94 Nd62ea719b43044cc9dd0c2390e792f45 rdf:first sg:person.016404105241.53
95 rdf:rest N3ab337482c65456f90fda89a85f77ccc
96 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
97 schema:name Information and Computing Sciences
98 rdf:type schema:DefinedTerm
99 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
100 schema:name Computation Theory and Mathematics
101 rdf:type schema:DefinedTerm
102 sg:person.013206304341.94 schema:affiliation grid-institutes:grid.5328.c
103 schema:familyName Naya-Plasencia
104 schema:givenName María
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013206304341.94
106 rdf:type schema:Person
107 sg:person.016404105241.53 schema:affiliation grid-institutes:grid.410413.3
108 schema:familyName Grassi
109 schema:givenName Lorenzo
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016404105241.53
111 rdf:type schema:Person
112 sg:person.07436415541.40 schema:affiliation grid-institutes:grid.5328.c
113 schema:familyName Schrottenloher
114 schema:givenName André
115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07436415541.40
116 rdf:type schema:Person
117 grid-institutes:grid.410413.3 schema:alternateName IAIK, Graz University of Technology, Graz, Austria
118 schema:name IAIK, Graz University of Technology, Graz, Austria
119 rdf:type schema:Organization
120 grid-institutes:grid.5328.c schema:alternateName Inria, Paris, France
121 schema:name Inria, Paris, France
122 rdf:type schema:Organization
 




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


...