Incrementally Verifiable Computation via Incremental PCPs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2019-11-22

AUTHORS

Moni Naor , Omer Paneth , Guy N. Rothblum

ABSTRACT

If I commission a long computation, how can I check that the result is correct without re-doing the computation myself? This is the question that efficient verifiable computation deals with. In this work, we address the issue of verifying the computation as it unfolds. That is, at any intermediate point in the computation, I would like to see a proof that the current state is correct. Ideally, these proofs should be short, non-interactive, and easy to verify. In addition, the proof at each step should be generated efficiently by updating the previous proof, without recomputing the entire proof from scratch. This notion, known as incrementally verifiable computation, was introduced by Valiant [TCC 08] about a decade ago. Existing solutions follow the approach of recursive proof composition and can be based on strong and non-falsifiable cryptographic assumptions (so-called “knowledge assumptions”).In this work, we present a new framework for constructing incrementally verifiable computation schemes in both the publicly verifiable and designated-verifier settings. Our designated-verifier scheme is based on somewhat homomorphic encryption (which can be based on Learning with Errors) and our publicly verifiable scheme is based on the notion of zero-testable homomorphic encryption, which can be constructed from ideal multi-linear maps [Paneth and Rothblum, TCC 17].Our framework is anchored around the new notion of a probabilistically checkable proof (PCP) with incremental local updates. An incrementally updatable PCP proves the correctness of an ongoing computation, where after each computation step, the value of every symbol can be updated locally without reading any other symbol. This update results in a new PCP for the correctness of the next step in the computation. Our primary technical contribution is constructing such an incrementally updatable PCP. We show how to combine updatable PCPs with recently suggested (ordinary) verifiable computation to obtain our results. More... »

PAGES

552-576

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-030-36033-7_21

DOI

http://dx.doi.org/10.1007/978-3-030-36033-7_21

DIMENSIONS

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


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": "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": "Naor", 
        "givenName": "Moni", 
        "id": "sg:person.07776170271.83", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "MIT and Northeastern University, Cambridge, USA", 
          "id": "http://www.grid.ac/institutes/grid.261112.7", 
          "name": [
            "MIT and Northeastern University, Cambridge, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Paneth", 
        "givenName": "Omer", 
        "id": "sg:person.014073524511.68", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014073524511.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": "Rothblum", 
        "givenName": "Guy N.", 
        "id": "sg:person.014351474277.34", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014351474277.34"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2019-11-22", 
    "datePublishedReg": "2019-11-22", 
    "description": "Abstract\nIf I commission a long computation, how can I check that the result is correct without re-doing the computation myself? This is the question that efficient verifiable computation deals with. In this work, we address the issue of verifying the computation as it unfolds. That is, at any intermediate point in the computation, I would like to see a proof that the current state is correct. Ideally, these proofs should be short, non-interactive, and easy to verify. In addition, the proof at each step should be generated efficiently by updating the previous proof, without recomputing the entire proof from scratch. This notion, known as incrementally verifiable computation, was introduced by Valiant [TCC 08] about a decade ago. Existing solutions follow the approach of recursive proof composition and can be based on strong and non-falsifiable cryptographic assumptions (so-called \u201cknowledge assumptions\u201d).In this work, we present a new framework for constructing incrementally verifiable computation schemes in both the publicly verifiable and designated-verifier settings. Our designated-verifier scheme is based on somewhat homomorphic encryption (which can be based on Learning with Errors) and our publicly verifiable scheme is based on the notion of zero-testable homomorphic encryption, which can be constructed from ideal multi-linear maps [Paneth and Rothblum, TCC 17].Our framework is anchored around the new notion of a probabilistically checkable proof (PCP) with incremental local updates. An incrementally updatable PCP proves the correctness of an ongoing computation, where after each computation step, the value of every symbol can be updated locally without reading any other symbol. This update results in a new PCP for the correctness of the next step in the computation. Our primary technical contribution is constructing such an incrementally updatable PCP. We show how to combine updatable PCPs with recently suggested (ordinary) verifiable computation to obtain our results.", 
    "editor": [
      {
        "familyName": "Hofheinz", 
        "givenName": "Dennis", 
        "type": "Person"
      }, 
      {
        "familyName": "Rosen", 
        "givenName": "Alon", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-030-36033-7_21", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-030-36032-0", 
        "978-3-030-36033-7"
      ], 
      "name": "Theory of Cryptography", 
      "type": "Book"
    }, 
    "keywords": [
      "verifiable computation", 
      "homomorphic encryption", 
      "recursive proof composition", 
      "verifiable computation scheme", 
      "primary technical contribution", 
      "multi-linear maps", 
      "proof composition", 
      "verifiable scheme", 
      "cryptographic assumptions", 
      "computation steps", 
      "checkable proofs", 
      "ongoing computations", 
      "local updates", 
      "technical contribution", 
      "computation scheme", 
      "encryption", 
      "new framework", 
      "long computations", 
      "computation", 
      "entire proof", 
      "correctness", 
      "scheme", 
      "new PCP", 
      "new notion", 
      "current state", 
      "previous proofs", 
      "framework", 
      "proof", 
      "next step", 
      "intermediate points", 
      "update", 
      "scratch", 
      "Valiant", 
      "symbols", 
      "step", 
      "work", 
      "notion", 
      "maps", 
      "issues", 
      "solution", 
      "results", 
      "point", 
      "assumption", 
      "state", 
      "setting", 
      "contribution", 
      "decades", 
      "questions", 
      "addition", 
      "values", 
      "PCP", 
      "composition", 
      "approach", 
      "efficient verifiable computation", 
      "non-falsifiable cryptographic assumptions", 
      "designated-verifier settings", 
      "designated-verifier scheme", 
      "zero-testable homomorphic encryption", 
      "ideal multi-linear maps", 
      "incremental local updates", 
      "updatable PCP", 
      "Incremental PCPs"
    ], 
    "name": "Incrementally Verifiable Computation via Incremental PCPs", 
    "pagination": "552-576", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1122801604"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-030-36033-7_21"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-030-36033-7_21", 
      "https://app.dimensions.ai/details/publication/pub.1122801604"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:10", 
    "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_181.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-030-36033-7_21"
  }
]
 

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-36033-7_21'

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-36033-7_21'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-36033-7_21'

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-36033-7_21'


 

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

144 TRIPLES      23 PREDICATES      87 URIs      80 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-030-36033-7_21 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N290af0bec94847d1b00d8930602e0ded
4 schema:datePublished 2019-11-22
5 schema:datePublishedReg 2019-11-22
6 schema:description Abstract If I commission a long computation, how can I check that the result is correct without re-doing the computation myself? This is the question that efficient verifiable computation deals with. In this work, we address the issue of verifying the computation as it unfolds. That is, at any intermediate point in the computation, I would like to see a proof that the current state is correct. Ideally, these proofs should be short, non-interactive, and easy to verify. In addition, the proof at each step should be generated efficiently by updating the previous proof, without recomputing the entire proof from scratch. This notion, known as incrementally verifiable computation, was introduced by Valiant [TCC 08] about a decade ago. Existing solutions follow the approach of recursive proof composition and can be based on strong and non-falsifiable cryptographic assumptions (so-called “knowledge assumptions”).In this work, we present a new framework for constructing incrementally verifiable computation schemes in both the publicly verifiable and designated-verifier settings. Our designated-verifier scheme is based on somewhat homomorphic encryption (which can be based on Learning with Errors) and our publicly verifiable scheme is based on the notion of zero-testable homomorphic encryption, which can be constructed from ideal multi-linear maps [Paneth and Rothblum, TCC 17].Our framework is anchored around the new notion of a probabilistically checkable proof (PCP) with incremental local updates. An incrementally updatable PCP proves the correctness of an ongoing computation, where after each computation step, the value of every symbol can be updated locally without reading any other symbol. This update results in a new PCP for the correctness of the next step in the computation. Our primary technical contribution is constructing such an incrementally updatable PCP. We show how to combine updatable PCPs with recently suggested (ordinary) verifiable computation to obtain our results.
7 schema:editor N068f43050ae74ccab29fa3a85f36c68c
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N5bd51a5658b94846ac9f105de0b247ea
12 schema:keywords Incremental PCPs
13 PCP
14 Valiant
15 addition
16 approach
17 assumption
18 checkable proofs
19 composition
20 computation
21 computation scheme
22 computation steps
23 contribution
24 correctness
25 cryptographic assumptions
26 current state
27 decades
28 designated-verifier scheme
29 designated-verifier settings
30 efficient verifiable computation
31 encryption
32 entire proof
33 framework
34 homomorphic encryption
35 ideal multi-linear maps
36 incremental local updates
37 intermediate points
38 issues
39 local updates
40 long computations
41 maps
42 multi-linear maps
43 new PCP
44 new framework
45 new notion
46 next step
47 non-falsifiable cryptographic assumptions
48 notion
49 ongoing computations
50 point
51 previous proofs
52 primary technical contribution
53 proof
54 proof composition
55 questions
56 recursive proof composition
57 results
58 scheme
59 scratch
60 setting
61 solution
62 state
63 step
64 symbols
65 technical contribution
66 updatable PCP
67 update
68 values
69 verifiable computation
70 verifiable computation scheme
71 verifiable scheme
72 work
73 zero-testable homomorphic encryption
74 schema:name Incrementally Verifiable Computation via Incremental PCPs
75 schema:pagination 552-576
76 schema:productId N3d88219efbd64631ad6aff67a72bc6cb
77 N8a1cf0bbefdc43439ea2602474135149
78 schema:publisher N4c4e4f2da4e1499fa8c12f9c592c71ec
79 schema:sameAs https://app.dimensions.ai/details/publication/pub.1122801604
80 https://doi.org/10.1007/978-3-030-36033-7_21
81 schema:sdDatePublished 2022-01-01T19:10
82 schema:sdLicense https://scigraph.springernature.com/explorer/license/
83 schema:sdPublisher N7912a02c02d04b03a06d8473fbd7f37d
84 schema:url https://doi.org/10.1007/978-3-030-36033-7_21
85 sgo:license sg:explorer/license/
86 sgo:sdDataset chapters
87 rdf:type schema:Chapter
88 N068f43050ae74ccab29fa3a85f36c68c rdf:first Na51cc90cb7ce48e38b2f32d5820334a8
89 rdf:rest Ne37c0200e7dd4305897ba0a1907473ed
90 N290af0bec94847d1b00d8930602e0ded rdf:first sg:person.07776170271.83
91 rdf:rest Nce2cf6fe18484ad7a2a75ef63342292f
92 N3d88219efbd64631ad6aff67a72bc6cb schema:name doi
93 schema:value 10.1007/978-3-030-36033-7_21
94 rdf:type schema:PropertyValue
95 N4c4e4f2da4e1499fa8c12f9c592c71ec schema:name Springer Nature
96 rdf:type schema:Organisation
97 N5bd51a5658b94846ac9f105de0b247ea schema:isbn 978-3-030-36032-0
98 978-3-030-36033-7
99 schema:name Theory of Cryptography
100 rdf:type schema:Book
101 N7912a02c02d04b03a06d8473fbd7f37d schema:name Springer Nature - SN SciGraph project
102 rdf:type schema:Organization
103 N8a1cf0bbefdc43439ea2602474135149 schema:name dimensions_id
104 schema:value pub.1122801604
105 rdf:type schema:PropertyValue
106 Na51cc90cb7ce48e38b2f32d5820334a8 schema:familyName Hofheinz
107 schema:givenName Dennis
108 rdf:type schema:Person
109 Nc1efa64da89543d8987489bc882faccc rdf:first sg:person.014351474277.34
110 rdf:rest rdf:nil
111 Nce2cf6fe18484ad7a2a75ef63342292f rdf:first sg:person.014073524511.68
112 rdf:rest Nc1efa64da89543d8987489bc882faccc
113 Ncfa2ece59bdd490f8b48e1e26af3640d schema:familyName Rosen
114 schema:givenName Alon
115 rdf:type schema:Person
116 Ne37c0200e7dd4305897ba0a1907473ed rdf:first Ncfa2ece59bdd490f8b48e1e26af3640d
117 rdf:rest rdf:nil
118 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
119 schema:name Information and Computing Sciences
120 rdf:type schema:DefinedTerm
121 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
122 schema:name Computation Theory and Mathematics
123 rdf:type schema:DefinedTerm
124 sg:person.014073524511.68 schema:affiliation grid-institutes:grid.261112.7
125 schema:familyName Paneth
126 schema:givenName Omer
127 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014073524511.68
128 rdf:type schema:Person
129 sg:person.014351474277.34 schema:affiliation grid-institutes:grid.13992.30
130 schema:familyName Rothblum
131 schema:givenName Guy N.
132 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014351474277.34
133 rdf:type schema:Person
134 sg:person.07776170271.83 schema:affiliation grid-institutes:grid.13992.30
135 schema:familyName Naor
136 schema:givenName Moni
137 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83
138 rdf:type schema:Person
139 grid-institutes:grid.13992.30 schema:alternateName Weizmann Institute of Science, Rehovot, Israel
140 schema:name Weizmann Institute of Science, Rehovot, Israel
141 rdf:type schema:Organization
142 grid-institutes:grid.261112.7 schema:alternateName MIT and Northeastern University, Cambridge, USA
143 schema:name MIT and Northeastern University, Cambridge, USA
144 rdf:type schema:Organization
 




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


...