@prefix ns1: .
@prefix ns2: .
@prefix rdf: .
@prefix rdfs: .
@prefix xml: .
@prefix xsd: .
a ns1:Chapter ;
ns1:about ,
;
ns1:author ( ) ;
ns1:datePublished "2013" ;
ns1:datePublishedReg "2013-01-01" ;
ns1: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." ;
ns1:editor ( [ a ns1:Person ;
ns1:familyName "Sahai" ;
ns1:givenName "Amit" ] ) ;
ns1:genre "chapter" ;
ns1:inLanguage "en" ;
ns1:isAccessibleForFree true ;
ns1:isPartOf [ a ns1:Book ;
ns1:isbn "978-3-642-36593-5",
"978-3-642-36594-2" ;
ns1:name "Theory of Cryptography" ] ;
ns1:keywords "A.",
"PVC model",
"PVC scheme",
"Publicly Verifiable Computation",
"SCC construction",
"SCC model",
"SCC scheme",
"adaptive security",
"answers",
"clients",
"cloud setting",
"coefficient",
"computation",
"computation results",
"construction",
"correct computation",
"correct outcome",
"correctness",
"crucial performance properties",
"differentiation",
"dynamics computations",
"evaluation",
"expressive manipulations",
"function",
"function f",
"function’s public key",
"independent work",
"key",
"less time",
"linear-time computation",
"manipulation",
"model",
"multivariate polynomials",
"new model",
"number",
"optimal update",
"oracle model",
"outcomes",
"performance properties",
"point A.",
"polynomial evaluation",
"polynomials",
"properties",
"public key",
"queries",
"random oracle model",
"result v",
"results",
"scheme",
"security",
"server",
"setting",
"signature Σ",
"signatures",
"source",
"succinct signature σ",
"technique",
"time",
"untrusted server",
"update",
"valid signature",
"verifiable computation",
"work" ;
ns1:name "Signatures of Correct Computation" ;
ns1:pagination "222-242" ;
ns1:productId [ a ns1:PropertyValue ;
ns1:name "doi" ;
ns1:value "10.1007/978-3-642-36594-2_13" ],
[ a ns1:PropertyValue ;
ns1:name "dimensions_id" ;
ns1:value "pub.1027409438" ] ;
ns1:publisher [ a ns1:Organisation ;
ns1:name "Springer Nature" ] ;
ns1:sameAs ,
;
ns1:sdDatePublished "2022-01-01T19:17" ;
ns1:sdLicense "https://scigraph.springernature.com/explorer/license/" ;
ns1:sdPublisher [ a ns1:Organization ;
ns1:name "Springer Nature - SN SciGraph project" ] ;
ns1:url "https://doi.org/10.1007/978-3-642-36594-2_13" ;
ns2:license ;
ns2:sdDataset "chapters" .
a ns1:DefinedTerm ;
ns1:inDefinedTermSet ;
ns1:name "Information and Computing Sciences" .
a ns1:DefinedTerm ;
ns1:inDefinedTermSet ;
ns1:name "Computation Theory and Mathematics" .
a ns1:Person ;
ns1:affiliation ;
ns1:familyName "Papamanthou" ;
ns1:givenName "Charalampos" ;
ns1:sameAs .
a ns1:Person ;
ns1:affiliation ;
ns1:familyName "Shi" ;
ns1:givenName "Elaine" ;
ns1:sameAs .
a ns1:Person ;
ns1:affiliation ;
ns1:familyName "Tamassia" ;
ns1:givenName "Roberto" ;
ns1:sameAs .
a ns1:Organization ;
ns1:alternateName "Brown University, USA" ;
ns1:name "Brown University, USA" .
a ns1:Organization ;
ns1:alternateName "University of Maryland, USA" ;
ns1:name "University of Maryland, USA" .
a ns1:Organization ;
ns1:alternateName "UC Berkeley, USA" ;
ns1:name "UC Berkeley, USA" .