Signatures of Correct Computation View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2013

AUTHORS

Charalampos Papamanthou , Elaine Shi , Roberto Tamassia

ABSTRACT

We introduce Signatures of Correct Computation (SCC), a new model for verifying dynamic computations in cloud settings. In the SCC model, a trusted source outsources a function f to an untrusted server, along with a public key for that function (to be used during verification). The server can then produce a succinct signature σ vouching for the correctness of the computation of f, i.e., that some result v is indeed the correct outcome of the function f evaluated on some point a. There are two crucial performance properties that we want to guarantee in an SCC construction: (1) verifying the signature should take asymptotically less time than evaluating the function f; and (2) the public key should be efficiently updated whenever the function changes.We construct SCC schemes (satisfying the above two properties) supporting expressive manipulations over multivariate polynomials, such as polynomial evaluation and differentiation. Our constructions are adaptively secure in the random oracle model and achieve optimal updates, i.e., the function’s public key can be updated in time proportional to the number of updated coefficients, without performing a linear-time computation (in the size of the polynomial).We also show that signatures of correct computation imply Publicly Verifiable Computation (PVC), a model recently introduced in several concurrent and independent works. Roughly speaking, in the SCC model, any client can verify the signature σ and be convinced of some computation result, whereas in the PVC model only the client that issued a query (or anyone who trusts this client) can verify that the server returned a valid signature (proof) for the answer to the query. Our techniques can be readily adapted to construct PVC schemes with adaptive security, efficient updates and without the random oracle model. More... »

PAGES

222-242

Book

TITLE

Theory of Cryptography

ISBN

978-3-642-36593-5
978-3-642-36594-2

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-36594-2_13

DOI

http://dx.doi.org/10.1007/978-3-642-36594-2_13

DIMENSIONS

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


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": "UC Berkeley, USA", 
          "id": "http://www.grid.ac/institutes/grid.47840.3f", 
          "name": [
            "UC Berkeley, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Papamanthou", 
        "givenName": "Charalampos", 
        "id": "sg:person.010450677547.30", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010450677547.30"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Maryland, USA", 
          "id": "http://www.grid.ac/institutes/grid.410443.6", 
          "name": [
            "University of Maryland, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Shi", 
        "givenName": "Elaine", 
        "id": "sg:person.014706274717.52", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014706274717.52"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Brown University, USA", 
          "id": "http://www.grid.ac/institutes/grid.40263.33", 
          "name": [
            "Brown University, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tamassia", 
        "givenName": "Roberto", 
        "id": "sg:person.0674326220.33", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0674326220.33"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2013", 
    "datePublishedReg": "2013-01-01", 
    "description": "We introduce Signatures of Correct Computation (SCC), a new model for verifying dynamic computations in cloud settings. In the SCC model, a trusted source outsources a function f to an untrusted server, along with a public key for that function (to be used during verification). The server can then produce a succinct signature \u03c3 vouching for the correctness of the computation of f, i.e., that some result v is indeed the correct outcome of the function f evaluated on some point a. There are two crucial performance properties that we want to guarantee in an SCC construction: (1)\u00a0verifying the signature should take asymptotically less time than evaluating the function f; and (2)\u00a0the public key should be efficiently updated whenever the function changes.We construct SCC schemes (satisfying the above two properties) supporting expressive manipulations over multivariate polynomials, such as polynomial evaluation and differentiation. Our constructions are adaptively secure in the random oracle model and achieve optimal updates, i.e., the function\u2019s public key can be updated in time proportional to the number of updated coefficients, without performing a linear-time computation (in the size of the polynomial).We also show that signatures of correct computation imply Publicly Verifiable Computation (PVC), a model recently introduced in several concurrent and independent works. Roughly speaking, in the SCC model, any client can verify the signature \u03c3 and be convinced of some computation result, whereas in the PVC model only the client that issued a query (or anyone who trusts this client) can verify that the server returned a valid signature (proof) for the answer to the query. Our techniques can be readily adapted to construct PVC schemes with adaptive security, efficient updates and without the random oracle model.", 
    "editor": [
      {
        "familyName": "Sahai", 
        "givenName": "Amit", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-36594-2_13", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-36593-5", 
        "978-3-642-36594-2"
      ], 
      "name": "Theory of Cryptography", 
      "type": "Book"
    }, 
    "keywords": [
      "random oracle model", 
      "public key", 
      "oracle model", 
      "correct computation", 
      "linear-time computation", 
      "untrusted server", 
      "verifiable computation", 
      "cloud setting", 
      "adaptive security", 
      "PVC scheme", 
      "optimal update", 
      "SCC scheme", 
      "valid signature", 
      "server", 
      "polynomial evaluation", 
      "queries", 
      "computation", 
      "dynamics computations", 
      "multivariate polynomials", 
      "computation results", 
      "key", 
      "scheme", 
      "correct outcome", 
      "clients", 
      "less time", 
      "performance properties", 
      "security", 
      "correctness", 
      "independent work", 
      "new model", 
      "model", 
      "update", 
      "signatures", 
      "function f", 
      "PVC model", 
      "construction", 
      "technique", 
      "time", 
      "work", 
      "answers", 
      "manipulation", 
      "polynomials", 
      "evaluation", 
      "number", 
      "function", 
      "results", 
      "setting", 
      "source", 
      "signature \u03a3", 
      "coefficient", 
      "properties", 
      "point A.", 
      "SCC model", 
      "outcomes", 
      "differentiation", 
      "A.", 
      "succinct signature \u03c3", 
      "result v", 
      "crucial performance properties", 
      "SCC construction", 
      "expressive manipulations", 
      "function\u2019s public key", 
      "Publicly Verifiable Computation"
    ], 
    "name": "Signatures of Correct Computation", 
    "pagination": "222-242", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1027409438"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-36594-2_13"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-36594-2_13", 
      "https://app.dimensions.ai/details/publication/pub.1027409438"
    ], 
    "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_285.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-36594-2_13"
  }
]
 

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-642-36594-2_13'

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-642-36594-2_13'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-36594-2_13'

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-642-36594-2_13'


 

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

143 TRIPLES      23 PREDICATES      89 URIs      82 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-36594-2_13 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Ncb8e15255f3b4076b17beb5b56979f07
4 schema:datePublished 2013
5 schema:datePublishedReg 2013-01-01
6 schema:description We introduce Signatures of Correct Computation (SCC), a new model for verifying dynamic computations in cloud settings. In the SCC model, a trusted source outsources a function f to an untrusted server, along with a public key for that function (to be used during verification). The server can then produce a succinct signature σ vouching for the correctness of the computation of f, i.e., that some result v is indeed the correct outcome of the function f evaluated on some point a. There are two crucial performance properties that we want to guarantee in an SCC construction: (1) verifying the signature should take asymptotically less time than evaluating the function f; and (2) the public key should be efficiently updated whenever the function changes.We construct SCC schemes (satisfying the above two properties) supporting expressive manipulations over multivariate polynomials, such as polynomial evaluation and differentiation. Our constructions are adaptively secure in the random oracle model and achieve optimal updates, i.e., the function’s public key can be updated in time proportional to the number of updated coefficients, without performing a linear-time computation (in the size of the polynomial).We also show that signatures of correct computation imply Publicly Verifiable Computation (PVC), a model recently introduced in several concurrent and independent works. Roughly speaking, in the SCC model, any client can verify the signature σ and be convinced of some computation result, whereas in the PVC model only the client that issued a query (or anyone who trusts this client) can verify that the server returned a valid signature (proof) for the answer to the query. Our techniques can be readily adapted to construct PVC schemes with adaptive security, efficient updates and without the random oracle model.
7 schema:editor Ndeca307e6c544dc484cc182e48db3db1
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N3c2c412c10e641bfa0aae937f27261b5
12 schema:keywords A.
13 PVC model
14 PVC scheme
15 Publicly Verifiable Computation
16 SCC construction
17 SCC model
18 SCC scheme
19 adaptive security
20 answers
21 clients
22 cloud setting
23 coefficient
24 computation
25 computation results
26 construction
27 correct computation
28 correct outcome
29 correctness
30 crucial performance properties
31 differentiation
32 dynamics computations
33 evaluation
34 expressive manipulations
35 function
36 function f
37 function’s public key
38 independent work
39 key
40 less time
41 linear-time computation
42 manipulation
43 model
44 multivariate polynomials
45 new model
46 number
47 optimal update
48 oracle model
49 outcomes
50 performance properties
51 point A.
52 polynomial evaluation
53 polynomials
54 properties
55 public key
56 queries
57 random oracle model
58 result v
59 results
60 scheme
61 security
62 server
63 setting
64 signature Σ
65 signatures
66 source
67 succinct signature σ
68 technique
69 time
70 untrusted server
71 update
72 valid signature
73 verifiable computation
74 work
75 schema:name Signatures of Correct Computation
76 schema:pagination 222-242
77 schema:productId N1cd7502589cd40e09d31830c7d886c55
78 N4c8902cf81d34371872cd3ed430d7ed4
79 schema:publisher N768456a3f3774bb3a979284c1d8105d0
80 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027409438
81 https://doi.org/10.1007/978-3-642-36594-2_13
82 schema:sdDatePublished 2022-01-01T19:17
83 schema:sdLicense https://scigraph.springernature.com/explorer/license/
84 schema:sdPublisher Ne27ec46280044f5bbd38429b036240fe
85 schema:url https://doi.org/10.1007/978-3-642-36594-2_13
86 sgo:license sg:explorer/license/
87 sgo:sdDataset chapters
88 rdf:type schema:Chapter
89 N1cd7502589cd40e09d31830c7d886c55 schema:name dimensions_id
90 schema:value pub.1027409438
91 rdf:type schema:PropertyValue
92 N3c2c412c10e641bfa0aae937f27261b5 schema:isbn 978-3-642-36593-5
93 978-3-642-36594-2
94 schema:name Theory of Cryptography
95 rdf:type schema:Book
96 N4800ce4e19c441d4a97aec0106618b57 rdf:first sg:person.014706274717.52
97 rdf:rest N4d285b620aea488a887144aad8f02560
98 N4c8902cf81d34371872cd3ed430d7ed4 schema:name doi
99 schema:value 10.1007/978-3-642-36594-2_13
100 rdf:type schema:PropertyValue
101 N4d285b620aea488a887144aad8f02560 rdf:first sg:person.0674326220.33
102 rdf:rest rdf:nil
103 N768456a3f3774bb3a979284c1d8105d0 schema:name Springer Nature
104 rdf:type schema:Organisation
105 N9db6c28f8b7a4309992ad9a98188018e schema:familyName Sahai
106 schema:givenName Amit
107 rdf:type schema:Person
108 Ncb8e15255f3b4076b17beb5b56979f07 rdf:first sg:person.010450677547.30
109 rdf:rest N4800ce4e19c441d4a97aec0106618b57
110 Ndeca307e6c544dc484cc182e48db3db1 rdf:first N9db6c28f8b7a4309992ad9a98188018e
111 rdf:rest rdf:nil
112 Ne27ec46280044f5bbd38429b036240fe schema:name Springer Nature - SN SciGraph project
113 rdf:type schema:Organization
114 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
115 schema:name Information and Computing Sciences
116 rdf:type schema:DefinedTerm
117 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
118 schema:name Computation Theory and Mathematics
119 rdf:type schema:DefinedTerm
120 sg:person.010450677547.30 schema:affiliation grid-institutes:grid.47840.3f
121 schema:familyName Papamanthou
122 schema:givenName Charalampos
123 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010450677547.30
124 rdf:type schema:Person
125 sg:person.014706274717.52 schema:affiliation grid-institutes:grid.410443.6
126 schema:familyName Shi
127 schema:givenName Elaine
128 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014706274717.52
129 rdf:type schema:Person
130 sg:person.0674326220.33 schema:affiliation grid-institutes:grid.40263.33
131 schema:familyName Tamassia
132 schema:givenName Roberto
133 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0674326220.33
134 rdf:type schema:Person
135 grid-institutes:grid.40263.33 schema:alternateName Brown University, USA
136 schema:name Brown University, USA
137 rdf:type schema:Organization
138 grid-institutes:grid.410443.6 schema:alternateName University of Maryland, USA
139 schema:name University of Maryland, USA
140 rdf:type schema:Organization
141 grid-institutes:grid.47840.3f schema:alternateName UC Berkeley, USA
142 schema:name UC Berkeley, USA
143 rdf:type schema:Organization
 




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


...