|
|
|
1 | (4) |
|
|
|
1 | (1) |
|
|
|
2 | (1) |
|
|
|
3 | (2) |
|
|
|
3 | (2) |
|
|
|
5 | (8) |
|
2.1 Verifiable Computation |
|
|
5 | (1) |
|
2.2 Properties of Verifiable Computing Schemes |
|
|
6 | (7) |
|
|
|
7 | (1) |
|
|
|
8 | (2) |
|
|
|
10 | (1) |
|
|
|
10 | (3) |
|
3 Proof and Argument Based Verifiable Computing |
|
|
13 | (10) |
|
3.1 Introduction to Proof and Argument Based Approaches |
|
|
13 | (1) |
|
3.2 Interactive Proof Based Approaches |
|
|
14 | (2) |
|
3.2.1 Verifiable Computation with Massively Parallel Interactive Proofs |
|
|
15 | (1) |
|
3.2.2 Allspice: A Hybrid Architecture for Interactive Verifiable Computation |
|
|
15 | (1) |
|
3.3 Interactive Argument Based Approaches |
|
|
16 | (2) |
|
3.3.1 Pepper: Making Argument Systems for Outsourced Computation Practical (Sometimes) |
|
|
17 | (1) |
|
3.3.2 Ginger: Taking Proof-Based Verified Computation a Few Steps Closer to Practicality |
|
|
17 | (1) |
|
3.3.3 Zaatar: Resolving the Conflict Between Generality and Plausibility in Verified Computation |
|
|
17 | (1) |
|
3.3.4 Pantry: Verifying Computations with State |
|
|
17 | (1) |
|
3.3.5 River: Verifiable Computation with Reduced Informational Costs and Computational Costs |
|
|
18 | (1) |
|
3.4 Non-interactive Argument Based Approaches |
|
|
18 | (5) |
|
3.4.1 Pinocchio: Nearly Practical Verifiable Computation |
|
|
19 | (1) |
|
3.4.2 Geppetto: Versatile Verifiable Computation |
|
|
19 | (1) |
|
3.4.3 SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge |
|
|
20 | (1) |
|
3.4.4 Succinct Non-interactive Zero Knowledge for a von Neumann Architecture |
|
|
20 | (1) |
|
3.4.5 Buffet: Efficient RAM and Control Flow in Verifiable Outsourced Computation |
|
|
20 | (1) |
|
3.4.6 ADSNARK: Nearly Practical and Privacy-Preserving Proofs on Authenticated Data |
|
|
20 | (1) |
|
3.4.7 Block Programs: Improving Efficiency of Verifiable Computation for Circuits with Repeated Substructures |
|
|
21 | (1) |
|
|
|
21 | (2) |
|
4 Verifiable Computing from Fully Homomorphic Encryption |
|
|
23 | (4) |
|
4.1 Definitions for Fully Homomorphic Encryption |
|
|
23 | (1) |
|
4.2 Verifiable Computing Schemes Based on FHE |
|
|
24 | (3) |
|
4.2.1 Non-interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers |
|
|
24 | (1) |
|
4.2.2 Improved Delegation of Computation Using Fully Homomorphic Encryption |
|
|
25 | (1) |
|
|
|
25 | (2) |
|
5 Homomorphic Authenticators |
|
|
27 | (10) |
|
5.1 Definitions for Homomorphic Authenticators |
|
|
27 | (3) |
|
5.2 Verifiable Computing Schemes Based on MACs |
|
|
30 | (1) |
|
5.2.1 Verifiable Delegation of Computation on Outsourced Data |
|
|
30 | (1) |
|
5.2.2 Generalized Homomorphic MACs with Efficient Verification |
|
|
30 | (1) |
|
5.2.3 Efficiently Verifiable Computation on Encrypted Data |
|
|
31 | (1) |
|
5.3 Signature Based Verifiable Computing on Linear Functions |
|
|
31 | (1) |
|
5.3.1 Programmable Hash Functions Go Private: Constructions and Applications to (Homomorphic) Signatures with Shorter Public Keys |
|
|
31 | (1) |
|
5.4 Signature Based Verifiable Computing for Polynomial Functions |
|
|
32 | (1) |
|
5.4.1 Homomorphic Signatures with Efficient Verification for Polynomial Functions |
|
|
32 | (1) |
|
5.4.2 Algebraic (Trapdoor) One-Way Functions and Their Applications |
|
|
32 | (1) |
|
5.5 Signature Based Verifiable Computing Using Homomorphic Encryption |
|
|
33 | (4) |
|
|
|
34 | (3) |
|
6 Verifiable Computing Frameworks from Functional Encryption and Functional Signatures |
|
|
37 | (6) |
|
6.1 Verifiable Computation from Functional Encryption |
|
|
37 | (2) |
|
6.1.1 Verifiable Computation from Attribute Based Encryption |
|
|
38 | (1) |
|
6.1.2 Delegatable Homomorphic Encryption with Applications to Secure Outsourcing of Computation |
|
|
38 | (1) |
|
6.2 Verifiable Computation from Functional Signatures |
|
|
39 | (4) |
|
6.2.1 Functional Signatures and Pseudorandom Functions |
|
|
39 | (2) |
|
|
|
41 | (2) |
|
7 Verifiable Computing for Specific Applications |
|
|
43 | (6) |
|
7.1 From Secrecy to Soundness: Efficient Verification via Secure Computation |
|
|
43 | (1) |
|
7.2 Signatures of Correct Computation |
|
|
44 | (1) |
|
7.3 Efficient Techniques for Publicly Verifiable Delegation of Computation |
|
|
44 | (1) |
|
7.4 Efficient Computation Outsourcing for Inverting a Class of Homomorphic Functions |
|
|
45 | (1) |
|
7.5 Secure Delegation of Elliptic-Curve Pairing |
|
|
45 | (1) |
|
7.6 Efficiently Verifiable Computation on Encrypted Data |
|
|
46 | (1) |
|
7.7 Verifiable Delegation of Computation over Large Datasets |
|
|
46 | (1) |
|
7.8 Batch Verifiable Computation with Public Verifiability for Outsourcing Polynomials and Matrix Computations |
|
|
46 | (1) |
|
7.9 TrueSet: Nearly Practical Verifiable Set Computations |
|
|
46 | (3) |
|
|
|
47 | (2) |
|
8 Analysis of the State of the Art |
|
|
49 | (8) |
|
8.1 Security, Privacy, and Efficiency |
|
|
49 | (4) |
|
|
|
53 | (1) |
|
|
|
54 | (3) |
|
|
|
54 | (3) |
|
|
|
57 | (2) |
|
|
|
58 | (1) |
| A Assumptions |
|
59 | (3) |
| References |
|
62 | |
Lisainfo e-raamatute kohta