"ongoing computations" .
"verifiable scheme" .
.
"Weizmann Institute of Science, Rehovot, Israel" .
"contribution" .
_:N4a59ed0f0c7646ed9190e9a1716fc6e9 "pub.1122801604" .
.
_:N37faf53588ff4f1289cc36c3f7bd42d6 .
_:N27f311d0e6854df2b7a9abd462e7ef82 .
"proof" .
_:Nf003794d7dd6483da329bc462e126f0e "Hofheinz" .
"work" .
"issues" .
"local updates" .
"decades" .
_:N633af624e0d046d2ac312f80540a194c .
_:Ne3faf8b215e54f66bf19fd217b68ee8c .
.
"addition" .
"Valiant" .
"primary technical contribution" .
_:N83e9d535cd6f433a84dc6488d7513896 .
.
"homomorphic encryption" .
"Paneth" .
.
"MIT and Northeastern University, Cambridge, USA" .
"552-576" .
_:N396a0b42ffe34db8ba1f2a2b91c96e14 _:N37faf53588ff4f1289cc36c3f7bd42d6 .
"Omer" .
_:Nd0fe7451c94a4fbdbf7e8c56f687e402 .
_:Ne595563042f54ab18a98723af88e1224 .
_:Nf003794d7dd6483da329bc462e126f0e .
_:N83e9d535cd6f433a84dc6488d7513896 "10.1007/978-3-030-36033-7_21" .
_:N83e9d535cd6f433a84dc6488d7513896 "doi" .
_:N27f311d0e6854df2b7a9abd462e7ef82 _:Ne595563042f54ab18a98723af88e1224 .
"point" .
_:N9d7278b89f0f4c5caaf421ac8527d976 "978-3-030-36033-7" .
"verifiable computation scheme" .
_:N83e9d535cd6f433a84dc6488d7513896 .
"false"^^ .
"long computations" .
"encryption" .
"intermediate points" .
"new notion" .
_:N396a0b42ffe34db8ba1f2a2b91c96e14 .
"chapter" .
.
"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." .
.
"proof composition" .
"technical contribution" .
"verifiable computation" .
.
"https://scigraph.springernature.com/explorer/license/" .
"scheme" .
"current state" .
"computation scheme" .
_:Ne3faf8b215e54f66bf19fd217b68ee8c .
_:Nbb1e8d1dc73c40769adad03dcff1043b .
"questions" .
"Computation Theory and Mathematics" .
"checkable proofs" .
_:N633af624e0d046d2ac312f80540a194c .
"Guy N." .
"2019-11-22" .
"multi-linear maps" .
.
"recursive proof composition" .
"update" .
"step" .
.
"assumption" .
_:N4a59ed0f0c7646ed9190e9a1716fc6e9 .
.
"cryptographic assumptions" .
_:N37faf53588ff4f1289cc36c3f7bd42d6 "Rosen" .
.
"Efficient Verifiable Computation" .
"results" .
.
"composition" .
_:N9d7278b89f0f4c5caaf421ac8527d976 .
.
"values" .
"new framework" .
.
.
"previous proofs" .
_:Ne3faf8b215e54f66bf19fd217b68ee8c "Springer Nature - SN SciGraph project" .
_:N4a59ed0f0c7646ed9190e9a1716fc6e9 .
_:N633af624e0d046d2ac312f80540a194c "Springer Nature" .
"framework" .
"Naor" .
"maps" .
_:N9d7278b89f0f4c5caaf421ac8527d976 .
"MIT and Northeastern University, Cambridge, USA" .
.
.
"Weizmann Institute of Science, Rehovot, Israel" .
"2019-11-22" .
"next step" .
_:N9d7278b89f0f4c5caaf421ac8527d976 "978-3-030-36032-0" .
_:N37faf53588ff4f1289cc36c3f7bd42d6 "Alon" .
_:Ne595563042f54ab18a98723af88e1224 .
"Rothblum" .
"symbols" .
_:N4a59ed0f0c7646ed9190e9a1716fc6e9 "dimensions_id" .
.
"2022-05-10T10:38" .
"scratch" .
"en" .
"chapters" .
"computation steps" .
_:Nf003794d7dd6483da329bc462e126f0e "Dennis" .
_:N9d7278b89f0f4c5caaf421ac8527d976 "Theory of Cryptography" .
"entire proof" .
_:Nd0fe7451c94a4fbdbf7e8c56f687e402 _:N396a0b42ffe34db8ba1f2a2b91c96e14 .
"setting" .
.
_:Nd0fe7451c94a4fbdbf7e8c56f687e402 _:Nf003794d7dd6483da329bc462e126f0e .
"new PCP" .
"correctness" .
"PCP" .
_:Nbb1e8d1dc73c40769adad03dcff1043b .