List-Decoding of Linear Functions and Analysis of a Two-Round Zero-Knowledge Argument View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2004

AUTHORS

Cynthia Dwork , Ronen Shaltiel , Adam Smith , Luca Trevisan

ABSTRACT

Dwork and Stockmeyer showed 2-round zero-knowledge proof systems secure against provers which are resource-bounded during the interaction [6]. The resources considered are running time and advice (the amount of precomputed information). We re-cast this construction in the language of list-decoding. This perspective leads to the following improvements:We give a new, simpler analysis of the protocol’s unconditional security in the advice-bounded case. Like the original, the new analysis is asymptotically tight.When the prover is bounded in both time and advice, we substantially improve the analysis of [6]: we prove security under a worst-case (instead of average-case) hardness assumption. Specifically, we assume that there exists g ∈ DTIME(2s) such that g is hard in the worst case for MAM circuits of size \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O(2^{s(\frac{1}{2}+\gamma)})$\end{document} for some γ> 0. Here s is the input length and MAM corresponds the class of circuits which are verifiers in a 3-message interactive proof (with constant soundness error) in which the prover sends the first message. In contrast, Dwork and Stockmeyer require a function that is average-case hard for “proof auditors,” a model of computation which generalizes randomized, non-deterministic circuits.Our analyses rely on new results on list-decodability of codes whose codewords are linear functions from {0,1}ℓ to {0,1}ℓ. For (1), we show that the set of all linear transformations is a good list-decodable code. For (2), we give a new, non-deterministic list-decoding procedure which runs in time quasi-linear in ℓ. More... »

PAGES

101-120

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-24638-1_6

DOI

http://dx.doi.org/10.1007/978-3-540-24638-1_6

DIMENSIONS

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


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": "Microsoft Research, SVC, 1065 La Avenida, 94043, Mountain View, CA, USA", 
          "id": "http://www.grid.ac/institutes/grid.419815.0", 
          "name": [
            "Microsoft Research, SVC, 1065 La Avenida, 94043, Mountain View, CA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Dwork", 
        "givenName": "Cynthia", 
        "id": "sg:person.016065712157.59", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016065712157.59"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Applied Math, The Weizmann Institute of Science, 76100, Rehovot, Israel", 
          "id": "http://www.grid.ac/institutes/grid.13992.30", 
          "name": [
            "Department of Computer Science and Applied Math, The Weizmann Institute of Science, 76100, Rehovot, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Shaltiel", 
        "givenName": "Ronen", 
        "id": "sg:person.011461011646.82", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011461011646.82"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "MIT Computer Science and AI Lab, 02139, Cambridge, MA, USA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "MIT Computer Science and AI Lab, 02139, Cambridge, MA, USA"
          ], 
          "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"
      }, 
      {
        "affiliation": {
          "alternateName": "University of California, 94720, Berkeley, CA, USA", 
          "id": "http://www.grid.ac/institutes/grid.47840.3f", 
          "name": [
            "University of California, 94720, Berkeley, CA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Trevisan", 
        "givenName": "Luca", 
        "id": "sg:person.015761757701.03", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015761757701.03"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2004", 
    "datePublishedReg": "2004-01-01", 
    "description": "Dwork and Stockmeyer showed 2-round zero-knowledge proof systems secure against provers which are resource-bounded during the interaction [6]. The resources considered are running time and advice (the amount of precomputed information). We re-cast this construction in the language of list-decoding. This perspective leads to the following improvements:We give a new, simpler analysis of the protocol\u2019s unconditional security in the advice-bounded case. Like the original, the new analysis is asymptotically tight.When the prover is bounded in both time and advice, we substantially improve the analysis of [6]: we prove security under a worst-case (instead of average-case) hardness assumption. Specifically, we assume that there exists g\u2009\u2208\u2009DTIME(2s) such that g is hard in the worst case for MAM circuits of size \\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^{s(\\frac{1}{2}+\\gamma)})$\\end{document} for some \u03b3>\u20090. Here s is the input length and MAM corresponds the class of circuits which are verifiers in a 3-message interactive proof (with constant soundness error) in which the prover sends the first message. In contrast, Dwork and Stockmeyer require a function that is average-case hard for \u201cproof auditors,\u201d a model of computation which generalizes randomized, non-deterministic circuits.Our analyses rely on new results on list-decodability of codes whose codewords are linear functions from {0,1}\u2113 to {0,1}\u2113. For (1), we show that the set of all linear transformations is a good list-decodable code. For (2), we give a new, non-deterministic list-decoding procedure which runs in time quasi-linear in \u2113.", 
    "editor": [
      {
        "familyName": "Naor", 
        "givenName": "Moni", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-24638-1_6", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-21000-9", 
        "978-3-540-24638-1"
      ], 
      "name": "Theory of Cryptography", 
      "type": "Book"
    }, 
    "keywords": [
      "zero-knowledge proof system", 
      "unconditional security", 
      "model of computation", 
      "worst-case hardness assumption", 
      "interactive proofs", 
      "hardness assumption", 
      "proof system", 
      "list-decodable codes", 
      "provers", 
      "input length", 
      "list decoding", 
      "first message", 
      "worst case", 
      "security", 
      "knowledge argument", 
      "Dwork", 
      "code", 
      "class of circuits", 
      "verifier", 
      "following improvements", 
      "codewords", 
      "Stockmeyer", 
      "linear transformation", 
      "computation", 
      "messages", 
      "language", 
      "set", 
      "resources", 
      "proof", 
      "system", 
      "time", 
      "linear function", 
      "original", 
      "auditors", 
      "model", 
      "construction", 
      "simple analysis", 
      "new analysis", 
      "circuit", 
      "class", 
      "improvement", 
      "analysis", 
      "function", 
      "advice", 
      "assumption", 
      "perspective", 
      "transformation", 
      "new results", 
      "results", 
      "cases", 
      "interaction", 
      "procedure", 
      "size", 
      "zeros", 
      "argument", 
      "length", 
      "contrast", 
      "MAM"
    ], 
    "name": "List-Decoding of Linear Functions and Analysis of a Two-Round Zero-Knowledge Argument", 
    "pagination": "101-120", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1046096391"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-24638-1_6"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-24638-1_6", 
      "https://app.dimensions.ai/details/publication/pub.1046096391"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-06-01T22:30", 
    "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_220.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-24638-1_6"
  }
]
 

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-24638-1_6'

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-24638-1_6'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-24638-1_6'

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-24638-1_6'


 

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

148 TRIPLES      23 PREDICATES      84 URIs      77 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-24638-1_6 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author Na63035fd166f4a0d9471a69dfcce8584
4 schema:datePublished 2004
5 schema:datePublishedReg 2004-01-01
6 schema:description Dwork and Stockmeyer showed 2-round zero-knowledge proof systems secure against provers which are resource-bounded during the interaction [6]. The resources considered are running time and advice (the amount of precomputed information). We re-cast this construction in the language of list-decoding. This perspective leads to the following improvements:We give a new, simpler analysis of the protocol’s unconditional security in the advice-bounded case. Like the original, the new analysis is asymptotically tight.When the prover is bounded in both time and advice, we substantially improve the analysis of [6]: we prove security under a worst-case (instead of average-case) hardness assumption. Specifically, we assume that there exists g ∈ DTIME(2s) such that g is hard in the worst case for MAM circuits of size \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O(2^{s(\frac{1}{2}+\gamma)})$\end{document} for some γ> 0. Here s is the input length and MAM corresponds the class of circuits which are verifiers in a 3-message interactive proof (with constant soundness error) in which the prover sends the first message. In contrast, Dwork and Stockmeyer require a function that is average-case hard for “proof auditors,” a model of computation which generalizes randomized, non-deterministic circuits.Our analyses rely on new results on list-decodability of codes whose codewords are linear functions from {0,1}ℓ to {0,1}ℓ. For (1), we show that the set of all linear transformations is a good list-decodable code. For (2), we give a new, non-deterministic list-decoding procedure which runs in time quasi-linear in ℓ.
7 schema:editor Nb772d8715df144a78918c9adf1605f67
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N3c2e2cd86acb4dd89495dbdfd375bb44
12 schema:keywords Dwork
13 MAM
14 Stockmeyer
15 advice
16 analysis
17 argument
18 assumption
19 auditors
20 cases
21 circuit
22 class
23 class of circuits
24 code
25 codewords
26 computation
27 construction
28 contrast
29 first message
30 following improvements
31 function
32 hardness assumption
33 improvement
34 input length
35 interaction
36 interactive proofs
37 knowledge argument
38 language
39 length
40 linear function
41 linear transformation
42 list decoding
43 list-decodable codes
44 messages
45 model
46 model of computation
47 new analysis
48 new results
49 original
50 perspective
51 procedure
52 proof
53 proof system
54 provers
55 resources
56 results
57 security
58 set
59 simple analysis
60 size
61 system
62 time
63 transformation
64 unconditional security
65 verifier
66 worst case
67 worst-case hardness assumption
68 zero-knowledge proof system
69 zeros
70 schema:name List-Decoding of Linear Functions and Analysis of a Two-Round Zero-Knowledge Argument
71 schema:pagination 101-120
72 schema:productId N0c274966f01e4cc1a06b844117c8fb5b
73 Nbf315a90c73b4df4b717502f18c490b0
74 schema:publisher Nf6acb0b0974c4b6d87d77713310ba5dd
75 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046096391
76 https://doi.org/10.1007/978-3-540-24638-1_6
77 schema:sdDatePublished 2022-06-01T22:30
78 schema:sdLicense https://scigraph.springernature.com/explorer/license/
79 schema:sdPublisher Nf4a71f7e9b8444449d1be4ce3255f903
80 schema:url https://doi.org/10.1007/978-3-540-24638-1_6
81 sgo:license sg:explorer/license/
82 sgo:sdDataset chapters
83 rdf:type schema:Chapter
84 N05e96b8ad06b4959bd10e017f35d1e1d rdf:first sg:person.013307226666.21
85 rdf:rest Nd43eca877cd347da881f0d0b56e4cf16
86 N0c274966f01e4cc1a06b844117c8fb5b schema:name doi
87 schema:value 10.1007/978-3-540-24638-1_6
88 rdf:type schema:PropertyValue
89 N2287eb1e4faf45a3a3be4097b8c862e1 schema:familyName Naor
90 schema:givenName Moni
91 rdf:type schema:Person
92 N3c2e2cd86acb4dd89495dbdfd375bb44 schema:isbn 978-3-540-21000-9
93 978-3-540-24638-1
94 schema:name Theory of Cryptography
95 rdf:type schema:Book
96 N7643824a39a648faa47aca9971bf6e9b rdf:first sg:person.011461011646.82
97 rdf:rest N05e96b8ad06b4959bd10e017f35d1e1d
98 Na63035fd166f4a0d9471a69dfcce8584 rdf:first sg:person.016065712157.59
99 rdf:rest N7643824a39a648faa47aca9971bf6e9b
100 Nb772d8715df144a78918c9adf1605f67 rdf:first N2287eb1e4faf45a3a3be4097b8c862e1
101 rdf:rest rdf:nil
102 Nbf315a90c73b4df4b717502f18c490b0 schema:name dimensions_id
103 schema:value pub.1046096391
104 rdf:type schema:PropertyValue
105 Nd43eca877cd347da881f0d0b56e4cf16 rdf:first sg:person.015761757701.03
106 rdf:rest rdf:nil
107 Nf4a71f7e9b8444449d1be4ce3255f903 schema:name Springer Nature - SN SciGraph project
108 rdf:type schema:Organization
109 Nf6acb0b0974c4b6d87d77713310ba5dd schema:name Springer Nature
110 rdf:type schema:Organisation
111 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
112 schema:name Information and Computing Sciences
113 rdf:type schema:DefinedTerm
114 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
115 schema:name Data Format
116 rdf:type schema:DefinedTerm
117 sg:person.011461011646.82 schema:affiliation grid-institutes:grid.13992.30
118 schema:familyName Shaltiel
119 schema:givenName Ronen
120 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011461011646.82
121 rdf:type schema:Person
122 sg:person.013307226666.21 schema:affiliation grid-institutes:grid.116068.8
123 schema:familyName Smith
124 schema:givenName Adam
125 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013307226666.21
126 rdf:type schema:Person
127 sg:person.015761757701.03 schema:affiliation grid-institutes:grid.47840.3f
128 schema:familyName Trevisan
129 schema:givenName Luca
130 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015761757701.03
131 rdf:type schema:Person
132 sg:person.016065712157.59 schema:affiliation grid-institutes:grid.419815.0
133 schema:familyName Dwork
134 schema:givenName Cynthia
135 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016065712157.59
136 rdf:type schema:Person
137 grid-institutes:grid.116068.8 schema:alternateName MIT Computer Science and AI Lab, 02139, Cambridge, MA, USA
138 schema:name MIT Computer Science and AI Lab, 02139, Cambridge, MA, USA
139 rdf:type schema:Organization
140 grid-institutes:grid.13992.30 schema:alternateName Department of Computer Science and Applied Math, The Weizmann Institute of Science, 76100, Rehovot, Israel
141 schema:name Department of Computer Science and Applied Math, The Weizmann Institute of Science, 76100, Rehovot, Israel
142 rdf:type schema:Organization
143 grid-institutes:grid.419815.0 schema:alternateName Microsoft Research, SVC, 1065 La Avenida, 94043, Mountain View, CA, USA
144 schema:name Microsoft Research, SVC, 1065 La Avenida, 94043, Mountain View, CA, USA
145 rdf:type schema:Organization
146 grid-institutes:grid.47840.3f schema:alternateName University of California, 94720, Berkeley, CA, USA
147 schema:name University of California, 94720, Berkeley, CA, USA
148 rdf:type schema:Organization
 




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


...