Optimal Merging in Quantum k-xor and k-sum Algorithms View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2020-05-01

AUTHORS

María Naya-Plasencia , André Schrottenloher

ABSTRACT

The k-xor or Generalized Birthday Problem aims at finding, given k lists of bit-strings, a k-tuple among them XORing to 0. If the lists are unbounded, the best classical (exponential) time complexity has withstood since Wagner’s CRYPTO 2002 paper. If the lists are bounded (of the same size) and such that there is a single solution, the dissection algorithms of Dinur et al. (CRYPTO 2012) improve the memory usage over a simple meet-in-the-middle.In this paper, we study quantum algorithms for the k-xor problem. With unbounded lists and quantum access, we improve previous work by Grassi et al. (ASIACRYPT 2018) for almost all k. Next, we extend our study to lists of any size and with classical access only.We define a set of “merging trees” which represent the best known strategies for quantum and classical merging in k-xor algorithms, and prove that our method is optimal among these. Our complexities are confirmed by a Mixed Integer Linear Program that computes the best strategy for a given k-xor problem. All our algorithms apply also when considering modular additions instead of bitwise xors.This framework enables us to give new improved quantum k-xor algorithms for all k and list sizes. Applications include the subset-sum problem, LPN with limited memory and the multiple-encryption problem. More... »

PAGES

311-340

Book

TITLE

Advances in Cryptology – EUROCRYPT 2020

ISBN

978-3-030-45723-5
978-3-030-45724-2

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-030-45724-2_11

DOI

http://dx.doi.org/10.1007/978-3-030-45724-2_11

DIMENSIONS

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


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": [
            "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": "2020-05-01", 
    "datePublishedReg": "2020-05-01", 
    "description": "The k-xor or Generalized Birthday Problem aims at finding, given k lists of bit-strings, a k-tuple among them XORing to 0. If the lists are unbounded, the best classical (exponential) time complexity has withstood since Wagner\u2019s CRYPTO 2002 paper. If the lists are bounded (of the same size) and such that there is a single solution, the dissection algorithms of Dinur et al. (CRYPTO 2012) improve the memory usage over a simple meet-in-the-middle.In this paper, we study quantum algorithms for the k-xor problem. With unbounded lists and quantum access, we improve previous work by Grassi et al. (ASIACRYPT 2018) for almost all k. Next, we extend our study to lists of any size and with classical access only.We define a set of \u201cmerging trees\u201d which represent the best known strategies for quantum and classical merging in k-xor algorithms, and prove that our method is optimal among these. Our complexities are confirmed by a Mixed Integer Linear Program that computes the best strategy for a given k-xor problem. All our algorithms apply also when considering modular additions instead of bitwise xors.This framework enables us to give new improved quantum k-xor algorithms for all k and list sizes. Applications include the subset-sum problem, LPN with limited memory and the multiple-encryption problem.", 
    "editor": [
      {
        "familyName": "Canteaut", 
        "givenName": "Anne", 
        "type": "Person"
      }, 
      {
        "familyName": "Ishai", 
        "givenName": "Yuval", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-030-45724-2_11", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-030-45723-5", 
        "978-3-030-45724-2"
      ], 
      "name": "Advances in Cryptology \u2013 EUROCRYPT 2020", 
      "type": "Book"
    }, 
    "keywords": [
      "k-XOR", 
      "mixed integer linear program", 
      "generalized birthday problem", 
      "integer linear program", 
      "quantum algorithms", 
      "linear program", 
      "subset sum problem", 
      "k lists", 
      "birthday problem", 
      "dissection algorithm", 
      "time complexity", 
      "classical access", 
      "k-tuples", 
      "single solution", 
      "et al", 
      "algorithm", 
      "problem", 
      "Dinur et al", 
      "modular addition", 
      "bitwise XOR", 
      "complexity", 
      "memory usage", 
      "previous work", 
      "Grassi et al", 
      "quantum", 
      "limited memory", 
      "optimal merging", 
      "merging", 
      "solution", 
      "list size", 
      "set", 
      "XORing", 
      "al", 
      "framework", 
      "applications", 
      "size", 
      "Wagner", 
      "work", 
      "known strategies", 
      "XOR", 
      "meet", 
      "trees", 
      "best strategy", 
      "list", 
      "strategies", 
      "usage", 
      "addition", 
      "memory", 
      "program", 
      "LPN", 
      "study", 
      "middle", 
      "unbounded lists", 
      "access", 
      "method", 
      "paper"
    ], 
    "name": "Optimal Merging in Quantum k-xor and k-sum Algorithms", 
    "pagination": "311-340", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1127311382"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-030-45724-2_11"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-030-45724-2_11", 
      "https://app.dimensions.ai/details/publication/pub.1127311382"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-10-01T06:54", 
    "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_186.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-030-45724-2_11"
  }
]
 

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-45724-2_11'

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-45724-2_11'

Turtle is a human-readable linked data format.

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

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-45724-2_11'


 

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

127 TRIPLES      22 PREDICATES      80 URIs      73 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-030-45724-2_11 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Ncdc9cf23a86c479ebc6b190ced9cc806
4 schema:datePublished 2020-05-01
5 schema:datePublishedReg 2020-05-01
6 schema:description The k-xor or Generalized Birthday Problem aims at finding, given k lists of bit-strings, a k-tuple among them XORing to 0. If the lists are unbounded, the best classical (exponential) time complexity has withstood since Wagner’s CRYPTO 2002 paper. If the lists are bounded (of the same size) and such that there is a single solution, the dissection algorithms of Dinur et al. (CRYPTO 2012) improve the memory usage over a simple meet-in-the-middle.In this paper, we study quantum algorithms for the k-xor problem. With unbounded lists and quantum access, we improve previous work by Grassi et al. (ASIACRYPT 2018) for almost all k. Next, we extend our study to lists of any size and with classical access only.We define a set of “merging trees” which represent the best known strategies for quantum and classical merging in k-xor algorithms, and prove that our method is optimal among these. Our complexities are confirmed by a Mixed Integer Linear Program that computes the best strategy for a given k-xor problem. All our algorithms apply also when considering modular additions instead of bitwise xors.This framework enables us to give new improved quantum k-xor algorithms for all k and list sizes. Applications include the subset-sum problem, LPN with limited memory and the multiple-encryption problem.
7 schema:editor N4cc810ee6b5e45a99ebff6e672c68892
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N540f4ea2f681417995b07172241e612a
11 schema:keywords Dinur et al
12 Grassi et al
13 LPN
14 Wagner
15 XOR
16 XORing
17 access
18 addition
19 al
20 algorithm
21 applications
22 best strategy
23 birthday problem
24 bitwise XOR
25 classical access
26 complexity
27 dissection algorithm
28 et al
29 framework
30 generalized birthday problem
31 integer linear program
32 k lists
33 k-XOR
34 k-tuples
35 known strategies
36 limited memory
37 linear program
38 list
39 list size
40 meet
41 memory
42 memory usage
43 merging
44 method
45 middle
46 mixed integer linear program
47 modular addition
48 optimal merging
49 paper
50 previous work
51 problem
52 program
53 quantum
54 quantum algorithms
55 set
56 single solution
57 size
58 solution
59 strategies
60 study
61 subset sum problem
62 time complexity
63 trees
64 unbounded lists
65 usage
66 work
67 schema:name Optimal Merging in Quantum k-xor and k-sum Algorithms
68 schema:pagination 311-340
69 schema:productId N8e5f714b5a2b4b29a44b907a99dcb627
70 Nb273fd4bfe81437dae8e4cb34e3af90e
71 schema:publisher N75fea15dcc344915a4547cceadc84364
72 schema:sameAs https://app.dimensions.ai/details/publication/pub.1127311382
73 https://doi.org/10.1007/978-3-030-45724-2_11
74 schema:sdDatePublished 2022-10-01T06:54
75 schema:sdLicense https://scigraph.springernature.com/explorer/license/
76 schema:sdPublisher Nd1796ebbfe7c4ac5821464d654e56903
77 schema:url https://doi.org/10.1007/978-3-030-45724-2_11
78 sgo:license sg:explorer/license/
79 sgo:sdDataset chapters
80 rdf:type schema:Chapter
81 N02f254b6a0fc448ba5977de2e1af0517 schema:familyName Ishai
82 schema:givenName Yuval
83 rdf:type schema:Person
84 N4cc810ee6b5e45a99ebff6e672c68892 rdf:first Nabbd83444898435bac8e8eb514c9f9aa
85 rdf:rest N64ecebc1608e41dab1bc281548326d6c
86 N540f4ea2f681417995b07172241e612a schema:isbn 978-3-030-45723-5
87 978-3-030-45724-2
88 schema:name Advances in Cryptology – EUROCRYPT 2020
89 rdf:type schema:Book
90 N642f8c9f27ae43f09f75be597dc7d5ec rdf:first sg:person.07436415541.40
91 rdf:rest rdf:nil
92 N64ecebc1608e41dab1bc281548326d6c rdf:first N02f254b6a0fc448ba5977de2e1af0517
93 rdf:rest rdf:nil
94 N75fea15dcc344915a4547cceadc84364 schema:name Springer Nature
95 rdf:type schema:Organisation
96 N8e5f714b5a2b4b29a44b907a99dcb627 schema:name dimensions_id
97 schema:value pub.1127311382
98 rdf:type schema:PropertyValue
99 Nabbd83444898435bac8e8eb514c9f9aa schema:familyName Canteaut
100 schema:givenName Anne
101 rdf:type schema:Person
102 Nb273fd4bfe81437dae8e4cb34e3af90e schema:name doi
103 schema:value 10.1007/978-3-030-45724-2_11
104 rdf:type schema:PropertyValue
105 Ncdc9cf23a86c479ebc6b190ced9cc806 rdf:first sg:person.013206304341.94
106 rdf:rest N642f8c9f27ae43f09f75be597dc7d5ec
107 Nd1796ebbfe7c4ac5821464d654e56903 schema:name Springer Nature - SN SciGraph project
108 rdf:type schema:Organization
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.07436415541.40 schema:affiliation grid-institutes:grid.5328.c
121 schema:familyName Schrottenloher
122 schema:givenName André
123 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07436415541.40
124 rdf:type schema:Person
125 grid-institutes:grid.5328.c schema:alternateName Inria, Paris, France
126 schema:name Inria, Paris, France
127 rdf:type schema:Organization
 




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


...