Optimal Error Correction Against Computationally Bounded Noise View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2005

AUTHORS

Silvio Micali , Chris Peikert , Madhu Sudan , David A. Wilson

ABSTRACT

For computationally bounded adversarial models of error, we construct appealingly simple, efficient, cryptographic encoding and unique decoding schemes whose error-correction capability is much greater than classically possible. In particular:For binary alphabets, we construct positive-rate coding schemes which are uniquely decodable from a 1/2 – γerror rate for any constant γ> 0.For large alphabets, we construct coding schemes which are uniquely decodable from a \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$1 - \sqrt{R}$\end{document}error rate for any information rate R> 0. Our results are qualitatively stronger than related work: the construction works in the public-key model (requiring no shared secret key or joint local state) and allows the channel to know everything that the receiver knows. In addition, our techniques can potentially be used to construct coding schemes that have information rates approaching the Shannon limit. Finally, our construction is qualitatively optimal: we show that unique decoding under high error rates is impossible in several natural relaxations of our model. More... »

PAGES

1-16

Book

TITLE

Theory of Cryptography

ISBN

978-3-540-24573-5
978-3-540-30576-7

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-30576-7_1

DOI

http://dx.doi.org/10.1007/978-3-540-30576-7_1

DIMENSIONS

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


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": "CSAIL, MIT, 77 Massachusetts Ave, Building 32, 02139, Cambridge, MA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "CSAIL, MIT, 77 Massachusetts Ave, Building 32, 02139, Cambridge, MA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Micali", 
        "givenName": "Silvio", 
        "id": "sg:person.013514725641.60", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013514725641.60"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "CSAIL, MIT, 77 Massachusetts Ave, Building 32, 02139, Cambridge, MA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "CSAIL, MIT, 77 Massachusetts Ave, Building 32, 02139, Cambridge, MA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Peikert", 
        "givenName": "Chris", 
        "id": "sg:person.014661113217.35", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014661113217.35"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "CSAIL, MIT, 77 Massachusetts Ave, Building 32, 02139, Cambridge, MA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "CSAIL, MIT, 77 Massachusetts Ave, Building 32, 02139, Cambridge, MA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sudan", 
        "givenName": "Madhu", 
        "id": "sg:person.014663420265.17", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "CSAIL, MIT, 77 Massachusetts Ave, Building 32, 02139, Cambridge, MA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "CSAIL, MIT, 77 Massachusetts Ave, Building 32, 02139, Cambridge, MA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wilson", 
        "givenName": "David A.", 
        "id": "sg:person.012005031013.32", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012005031013.32"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2005", 
    "datePublishedReg": "2005-01-01", 
    "description": "For computationally bounded adversarial models of error, we construct appealingly simple, efficient, cryptographic encoding and unique decoding schemes whose error-correction capability is much greater than classically possible. In particular:For binary alphabets, we construct positive-rate coding schemes which are uniquely decodable from a 1/2 \u2013 \u03b3error rate for any constant \u03b3> 0.For large alphabets, we construct coding schemes which are uniquely decodable from a \\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}$1 - \\sqrt{R}$\\end{document}error rate for any information rate R> 0. Our results are qualitatively stronger than related work: the construction works in the public-key model (requiring no shared secret key or joint local state) and allows the channel to know everything that the receiver knows. In addition, our techniques can potentially be used to construct coding schemes that have information rates approaching the Shannon limit. Finally, our construction is qualitatively optimal: we show that unique decoding under high error rates is impossible in several natural relaxations of our model.", 
    "editor": [
      {
        "familyName": "Kilian", 
        "givenName": "Joe", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-30576-7_1", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-24573-5", 
        "978-3-540-30576-7"
      ], 
      "name": "Theory of Cryptography", 
      "type": "Book"
    }, 
    "keywords": [
      "public-key model", 
      "error-correction capability", 
      "optimal error correction", 
      "cryptographic encoding", 
      "adversarial model", 
      "coding scheme", 
      "decoding scheme", 
      "related work", 
      "high error rates", 
      "error correction", 
      "Shannon limit", 
      "large alphabets", 
      "unique decoding", 
      "error rate", 
      "information rate", 
      "natural relaxation", 
      "scheme", 
      "alphabet", 
      "decoding", 
      "binary alphabet", 
      "encoding", 
      "Computationally", 
      "capability", 
      "model", 
      "noise", 
      "construction", 
      "error", 
      "receiver", 
      "technique", 
      "work", 
      "channels", 
      "rate R", 
      "results", 
      "correction", 
      "rate", 
      "addition", 
      "relaxation", 
      "limit", 
      "unique decoding schemes", 
      "positive-rate coding schemes", 
      "information rate R"
    ], 
    "name": "Optimal Error Correction Against Computationally Bounded Noise", 
    "pagination": "1-16", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1001751083"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-30576-7_1"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-30576-7_1", 
      "https://app.dimensions.ai/details/publication/pub.1001751083"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:17", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_308.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-30576-7_1"
  }
]
 

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-540-30576-7_1'

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-540-30576-7_1'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-30576-7_1'

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-540-30576-7_1'


 

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

122 TRIPLES      23 PREDICATES      67 URIs      60 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-30576-7_1 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author N9518c9ad438f436cb30287f952445666
4 schema:datePublished 2005
5 schema:datePublishedReg 2005-01-01
6 schema:description For computationally bounded adversarial models of error, we construct appealingly simple, efficient, cryptographic encoding and unique decoding schemes whose error-correction capability is much greater than classically possible. In particular:For binary alphabets, we construct positive-rate coding schemes which are uniquely decodable from a 1/2 – γerror rate for any constant γ> 0.For large alphabets, we construct coding schemes which are uniquely decodable from a \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$1 - \sqrt{R}$\end{document}error rate for any information rate R> 0. Our results are qualitatively stronger than related work: the construction works in the public-key model (requiring no shared secret key or joint local state) and allows the channel to know everything that the receiver knows. In addition, our techniques can potentially be used to construct coding schemes that have information rates approaching the Shannon limit. Finally, our construction is qualitatively optimal: we show that unique decoding under high error rates is impossible in several natural relaxations of our model.
7 schema:editor N8e286f7b12df4603be21ed88d51071e5
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N37869f9efe2042b9842644c7ca8caff7
12 schema:keywords Computationally
13 Shannon limit
14 addition
15 adversarial model
16 alphabet
17 binary alphabet
18 capability
19 channels
20 coding scheme
21 construction
22 correction
23 cryptographic encoding
24 decoding
25 decoding scheme
26 encoding
27 error
28 error correction
29 error rate
30 error-correction capability
31 high error rates
32 information rate
33 information rate R
34 large alphabets
35 limit
36 model
37 natural relaxation
38 noise
39 optimal error correction
40 positive-rate coding schemes
41 public-key model
42 rate
43 rate R
44 receiver
45 related work
46 relaxation
47 results
48 scheme
49 technique
50 unique decoding
51 unique decoding schemes
52 work
53 schema:name Optimal Error Correction Against Computationally Bounded Noise
54 schema:pagination 1-16
55 schema:productId N1f8b8cab1a774b4daf245c60afb7aec1
56 N8935b7849ce740619f1234daecfc91fe
57 schema:publisher Nc37653a04e3449d9930af334f17ec6f9
58 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001751083
59 https://doi.org/10.1007/978-3-540-30576-7_1
60 schema:sdDatePublished 2022-01-01T19:17
61 schema:sdLicense https://scigraph.springernature.com/explorer/license/
62 schema:sdPublisher N5c67c4f8f0c1496d8f4150b711c05211
63 schema:url https://doi.org/10.1007/978-3-540-30576-7_1
64 sgo:license sg:explorer/license/
65 sgo:sdDataset chapters
66 rdf:type schema:Chapter
67 N06f1fb384e11457f8e0ac10170686ef1 rdf:first sg:person.012005031013.32
68 rdf:rest rdf:nil
69 N1f8b8cab1a774b4daf245c60afb7aec1 schema:name dimensions_id
70 schema:value pub.1001751083
71 rdf:type schema:PropertyValue
72 N37869f9efe2042b9842644c7ca8caff7 schema:isbn 978-3-540-24573-5
73 978-3-540-30576-7
74 schema:name Theory of Cryptography
75 rdf:type schema:Book
76 N5c67c4f8f0c1496d8f4150b711c05211 schema:name Springer Nature - SN SciGraph project
77 rdf:type schema:Organization
78 N8935b7849ce740619f1234daecfc91fe schema:name doi
79 schema:value 10.1007/978-3-540-30576-7_1
80 rdf:type schema:PropertyValue
81 N8e286f7b12df4603be21ed88d51071e5 rdf:first Ne32096ddc415445da59e453357c71865
82 rdf:rest rdf:nil
83 N9518c9ad438f436cb30287f952445666 rdf:first sg:person.013514725641.60
84 rdf:rest Ndf106bdf8f2342979d1b73609500763e
85 N9f2965906df24405ada7069e21974c85 rdf:first sg:person.014663420265.17
86 rdf:rest N06f1fb384e11457f8e0ac10170686ef1
87 Nc37653a04e3449d9930af334f17ec6f9 schema:name Springer Nature
88 rdf:type schema:Organisation
89 Ndf106bdf8f2342979d1b73609500763e rdf:first sg:person.014661113217.35
90 rdf:rest N9f2965906df24405ada7069e21974c85
91 Ne32096ddc415445da59e453357c71865 schema:familyName Kilian
92 schema:givenName Joe
93 rdf:type schema:Person
94 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
95 schema:name Information and Computing Sciences
96 rdf:type schema:DefinedTerm
97 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
98 schema:name Data Format
99 rdf:type schema:DefinedTerm
100 sg:person.012005031013.32 schema:affiliation grid-institutes:grid.116068.8
101 schema:familyName Wilson
102 schema:givenName David A.
103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012005031013.32
104 rdf:type schema:Person
105 sg:person.013514725641.60 schema:affiliation grid-institutes:grid.116068.8
106 schema:familyName Micali
107 schema:givenName Silvio
108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013514725641.60
109 rdf:type schema:Person
110 sg:person.014661113217.35 schema:affiliation grid-institutes:grid.116068.8
111 schema:familyName Peikert
112 schema:givenName Chris
113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014661113217.35
114 rdf:type schema:Person
115 sg:person.014663420265.17 schema:affiliation grid-institutes:grid.116068.8
116 schema:familyName Sudan
117 schema:givenName Madhu
118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17
119 rdf:type schema:Person
120 grid-institutes:grid.116068.8 schema:alternateName CSAIL, MIT, 77 Massachusetts Ave, Building 32, 02139, Cambridge, MA
121 schema:name CSAIL, MIT, 77 Massachusetts Ave, Building 32, 02139, Cambridge, MA
122 rdf:type schema:Organization
 




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


...