Approximate Quantum Error-Correcting Codes and Secret Sharing Schemes View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2005

AUTHORS

Claude Crépeau , Daniel Gottesman , Adam Smith

ABSTRACT

It is a standard result in the theory of quantum error- correcting codes that no code of length n can fix more than n/4 arbitrary errors, regardless of the dimension of the coding and encoded Hilbert spaces. However, this bound only applies to codes which recover the message exactly. Naively, one might expect that correcting errors to very high fidelity would only allow small violations of this bound. This intuition is incorrect: in this paper we describe quantum error-correcting codes capable of correcting up to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\lfloor(n - 1)/2\rfloor$\end{document} arbitrary errors with fidelity exponentially close to 1, at the price of increasing the size of the registers (i.e., the coding alphabet). This demonstrates a sharp distinction between exact and approximate quantum error correction. The codes have the property that any t components reveal no information about the message, and so they can also be viewed as error-tolerant secret sharing schemes.The construction has several interesting implications for cryptography and quantum information theory. First, it suggests that secret sharing is a better classical analogue to quantum error correction than is classical error correction. Second, it highlights an error in a purported proof that verifiable quantum secret sharing (VQSS) is impossible when the number of cheaters t is n/4. In particular, the construction directly yields an honest-dealer VQSS scheme for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$t= \lfloor(n - 1)/2\rfloor$\end{document}. We believe the codes could also potentially lead to improved protocols for dishonest-dealer VQSS and secure multi-party quantum computation.More generally, the construction illustrates a difference between exact and approximate requirements in quantum cryptography and (yet again) the delicacy of security proofs and impossibility results in the quantum model. More... »

PAGES

285-301

Book

TITLE

Advances in Cryptology – EUROCRYPT 2005

ISBN

978-3-540-25910-7
978-3-540-32055-5

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11426639_17

DOI

http://dx.doi.org/10.1007/11426639_17

DIMENSIONS

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


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/0804", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Data Format", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "McGill University, Montr\u00e9al, QC, Canada", 
          "id": "http://www.grid.ac/institutes/grid.14709.3b", 
          "name": [
            "McGill University, Montr\u00e9al, QC, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Cr\u00e9peau", 
        "givenName": "Claude", 
        "id": "sg:person.01127736412.71", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01127736412.71"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Perimeter Institute, Waterloo, ON, Canada", 
          "id": "http://www.grid.ac/institutes/grid.420198.6", 
          "name": [
            "Perimeter Institute, Waterloo, ON, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Gottesman", 
        "givenName": "Daniel", 
        "id": "sg:person.013605661215.68", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013605661215.68"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Weizmann Institute of Science, Rehovot, Israel", 
          "id": "http://www.grid.ac/institutes/grid.13992.30", 
          "name": [
            "Weizmann Institute of Science, Rehovot, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Smith", 
        "givenName": "Adam", 
        "id": "sg:person.013307226666.21", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013307226666.21"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2005", 
    "datePublishedReg": "2005-01-01", 
    "description": "It is a standard result in the theory of quantum error- correcting codes that no code of length n can fix more than n/4 arbitrary errors, regardless of the dimension of the coding and encoded Hilbert spaces. However, this bound only applies to codes which recover the message exactly. Naively, one might expect that correcting errors to very high fidelity would only allow small violations of this bound. This intuition is incorrect: in this paper we describe quantum error-correcting codes capable of correcting up to \\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}$\\lfloor(n - 1)/2\\rfloor$\\end{document} arbitrary errors with fidelity exponentially close to 1, at the price of increasing the size of the registers (i.e., the coding alphabet). This demonstrates a sharp distinction between exact and approximate quantum error correction. The codes have the property that any t components reveal no information about the message, and so they can also be viewed as error-tolerant secret sharing schemes.The construction has several interesting implications for cryptography and quantum information theory. First, it suggests that secret sharing is a better classical analogue to quantum error correction than is classical error correction. Second, it highlights an error in a purported proof that verifiable quantum secret sharing (VQSS) is impossible when the number of cheaters t is n/4. In particular, the construction directly yields an honest-dealer VQSS scheme for \\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}$t= \\lfloor(n - 1)/2\\rfloor$\\end{document}. We believe the codes could also potentially lead to improved protocols for dishonest-dealer VQSS and secure multi-party quantum computation.More generally, the construction illustrates a difference between exact and approximate requirements in quantum cryptography and (yet again) the delicacy of security proofs and impossibility results in the quantum model.", 
    "editor": [
      {
        "familyName": "Cramer", 
        "givenName": "Ronald", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11426639_17", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-25910-7", 
        "978-3-540-32055-5"
      ], 
      "name": "Advances in Cryptology \u2013 EUROCRYPT 2005", 
      "type": "Book"
    }, 
    "keywords": [
      "verifiable quantum secret sharing", 
      "secret sharing scheme", 
      "error-correcting codes", 
      "secret sharing", 
      "quantum error-correcting codes", 
      "sharing scheme", 
      "error correction", 
      "arbitrary errors", 
      "error correcting codes", 
      "security proof", 
      "classical error correction", 
      "quantum error correcting codes", 
      "quantum secret sharing", 
      "cryptography", 
      "quantum cryptography", 
      "information theory", 
      "impossibility results", 
      "purported proof", 
      "approximate quantum error correction", 
      "code", 
      "sharing", 
      "quantum error correction", 
      "approximate quantum error correcting codes", 
      "quantum information theory", 
      "quantum computation", 
      "scheme", 
      "messages", 
      "improved protocol", 
      "classical analog", 
      "quantum model", 
      "high fidelity", 
      "error", 
      "coding", 
      "small violations", 
      "length n", 
      "computation", 
      "proof", 
      "requirements", 
      "information", 
      "fidelity", 
      "approximate requirements", 
      "construction", 
      "protocol", 
      "intuition", 
      "interesting implications", 
      "Hilbert space", 
      "standard results", 
      "correction", 
      "space", 
      "T component", 
      "violation", 
      "model", 
      "results", 
      "theory", 
      "number", 
      "components", 
      "properties", 
      "dimensions", 
      "sharp distinction", 
      "prices", 
      "Register", 
      "size", 
      "distinction", 
      "analogues", 
      "delicacy", 
      "implications", 
      "paper", 
      "differences"
    ], 
    "name": "Approximate Quantum Error-Correcting Codes and Secret Sharing Schemes", 
    "pagination": "285-301", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1040777272"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11426639_17"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11426639_17", 
      "https://app.dimensions.ai/details/publication/pub.1040777272"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-06-01T22:33", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220601/entities/gbq_results/chapter/chapter_367.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11426639_17"
  }
]
 

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/11426639_17'

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/11426639_17'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11426639_17'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11426639_17'


 

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

148 TRIPLES      23 PREDICATES      94 URIs      87 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11426639_17 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author Na3ec88bbe8e745cf9e48ba2ad4f6a6a9
4 schema:datePublished 2005
5 schema:datePublishedReg 2005-01-01
6 schema:description It is a standard result in the theory of quantum error- correcting codes that no code of length n can fix more than n/4 arbitrary errors, regardless of the dimension of the coding and encoded Hilbert spaces. However, this bound only applies to codes which recover the message exactly. Naively, one might expect that correcting errors to very high fidelity would only allow small violations of this bound. This intuition is incorrect: in this paper we describe quantum error-correcting codes capable of correcting up to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\lfloor(n - 1)/2\rfloor$\end{document} arbitrary errors with fidelity exponentially close to 1, at the price of increasing the size of the registers (i.e., the coding alphabet). This demonstrates a sharp distinction between exact and approximate quantum error correction. The codes have the property that any t components reveal no information about the message, and so they can also be viewed as error-tolerant secret sharing schemes.The construction has several interesting implications for cryptography and quantum information theory. First, it suggests that secret sharing is a better classical analogue to quantum error correction than is classical error correction. Second, it highlights an error in a purported proof that verifiable quantum secret sharing (VQSS) is impossible when the number of cheaters t is n/4. In particular, the construction directly yields an honest-dealer VQSS scheme for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$t= \lfloor(n - 1)/2\rfloor$\end{document}. We believe the codes could also potentially lead to improved protocols for dishonest-dealer VQSS and secure multi-party quantum computation.More generally, the construction illustrates a difference between exact and approximate requirements in quantum cryptography and (yet again) the delicacy of security proofs and impossibility results in the quantum model.
7 schema:editor Ncf33109ffa894e80ba7767342d3b94b0
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nea4157a2819e48d0972dd7f45a49918e
12 schema:keywords Hilbert space
13 Register
14 T component
15 analogues
16 approximate quantum error correcting codes
17 approximate quantum error correction
18 approximate requirements
19 arbitrary errors
20 classical analog
21 classical error correction
22 code
23 coding
24 components
25 computation
26 construction
27 correction
28 cryptography
29 delicacy
30 differences
31 dimensions
32 distinction
33 error
34 error correcting codes
35 error correction
36 error-correcting codes
37 fidelity
38 high fidelity
39 implications
40 impossibility results
41 improved protocol
42 information
43 information theory
44 interesting implications
45 intuition
46 length n
47 messages
48 model
49 number
50 paper
51 prices
52 proof
53 properties
54 protocol
55 purported proof
56 quantum computation
57 quantum cryptography
58 quantum error correcting codes
59 quantum error correction
60 quantum error-correcting codes
61 quantum information theory
62 quantum model
63 quantum secret sharing
64 requirements
65 results
66 scheme
67 secret sharing
68 secret sharing scheme
69 security proof
70 sharing
71 sharing scheme
72 sharp distinction
73 size
74 small violations
75 space
76 standard results
77 theory
78 verifiable quantum secret sharing
79 violation
80 schema:name Approximate Quantum Error-Correcting Codes and Secret Sharing Schemes
81 schema:pagination 285-301
82 schema:productId N202b7d58151c4cd2b6cbe5fd0dbee2f7
83 Na2aa1dafdc394afdb21142e89d199d68
84 schema:publisher Na22ceb1b6c29429f95b444b3616c418a
85 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040777272
86 https://doi.org/10.1007/11426639_17
87 schema:sdDatePublished 2022-06-01T22:33
88 schema:sdLicense https://scigraph.springernature.com/explorer/license/
89 schema:sdPublisher N972219798f7f4abc9f81c6144c3e5bd5
90 schema:url https://doi.org/10.1007/11426639_17
91 sgo:license sg:explorer/license/
92 sgo:sdDataset chapters
93 rdf:type schema:Chapter
94 N202b7d58151c4cd2b6cbe5fd0dbee2f7 schema:name doi
95 schema:value 10.1007/11426639_17
96 rdf:type schema:PropertyValue
97 N972219798f7f4abc9f81c6144c3e5bd5 schema:name Springer Nature - SN SciGraph project
98 rdf:type schema:Organization
99 Na22ceb1b6c29429f95b444b3616c418a schema:name Springer Nature
100 rdf:type schema:Organisation
101 Na2aa1dafdc394afdb21142e89d199d68 schema:name dimensions_id
102 schema:value pub.1040777272
103 rdf:type schema:PropertyValue
104 Na3ec88bbe8e745cf9e48ba2ad4f6a6a9 rdf:first sg:person.01127736412.71
105 rdf:rest Ndae5ba09586c4b9f88ce2ba854974749
106 Nb73093843ee54812b122f81d4d2d2593 schema:familyName Cramer
107 schema:givenName Ronald
108 rdf:type schema:Person
109 Ncf33109ffa894e80ba7767342d3b94b0 rdf:first Nb73093843ee54812b122f81d4d2d2593
110 rdf:rest rdf:nil
111 Ndae5ba09586c4b9f88ce2ba854974749 rdf:first sg:person.013605661215.68
112 rdf:rest Nef861a6e12f94e88bd1b5462fd27f7a5
113 Nea4157a2819e48d0972dd7f45a49918e schema:isbn 978-3-540-25910-7
114 978-3-540-32055-5
115 schema:name Advances in Cryptology – EUROCRYPT 2005
116 rdf:type schema:Book
117 Nef861a6e12f94e88bd1b5462fd27f7a5 rdf:first sg:person.013307226666.21
118 rdf:rest rdf:nil
119 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
120 schema:name Information and Computing Sciences
121 rdf:type schema:DefinedTerm
122 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
123 schema:name Data Format
124 rdf:type schema:DefinedTerm
125 sg:person.01127736412.71 schema:affiliation grid-institutes:grid.14709.3b
126 schema:familyName Crépeau
127 schema:givenName Claude
128 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01127736412.71
129 rdf:type schema:Person
130 sg:person.013307226666.21 schema:affiliation grid-institutes:grid.13992.30
131 schema:familyName Smith
132 schema:givenName Adam
133 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013307226666.21
134 rdf:type schema:Person
135 sg:person.013605661215.68 schema:affiliation grid-institutes:grid.420198.6
136 schema:familyName Gottesman
137 schema:givenName Daniel
138 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013605661215.68
139 rdf:type schema:Person
140 grid-institutes:grid.13992.30 schema:alternateName Weizmann Institute of Science, Rehovot, Israel
141 schema:name Weizmann Institute of Science, Rehovot, Israel
142 rdf:type schema:Organization
143 grid-institutes:grid.14709.3b schema:alternateName McGill University, Montréal, QC, Canada
144 schema:name McGill University, Montréal, QC, Canada
145 rdf:type schema:Organization
146 grid-institutes:grid.420198.6 schema:alternateName Perimeter Institute, Waterloo, ON, Canada
147 schema:name Perimeter Institute, Waterloo, ON, Canada
148 rdf:type schema:Organization
 




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


...