Project topics and materials
Get Complete Project Material File(s) Now! »
Requirements and Features for Veriable Computation Protocols
From the above space agency scenario, we are able to extract the requirements and desired features for a VC scheme. The proofs of correct computation must satisfy two security requirements: they must be correct (if the cloud server is honest, the agency will always accept the proofs) and sound (a malicious cloud server cannot make the agency accept an incorrect result). Furthermore, it is essential that the verication of the results of outsourced computation must induce less costs than having the data owner process the space data locally. Otherwise, the migration to a cloud infrastructure would not be protable for the space agency; on the contrary, it should help the agency save costs in processing. This illustrates another requirement: the eciency requirement. Besides, the space agency would like to delegate to its researchers and to other collaborators (such as researchers from universities abroad, subcontractors, etc.) the capability to execute the outsourced operations (evaluate polynomial, compute matrix multiplication, search for keywords). These third-party users will also be empowered with the capability to verify the results of these operations. Consequently, the space agency needs a framework that ensures public delegatability and public veriability of outsourced operations.
Eciency Requirement. This requirement can be expressed in the following terms: In order not to waste the advantages of outsourcing the computation to the cloud, the cost for the user of submitting computation requests and verifying the cryptographic proofs must be less expensive than running the computation locally from scratch. This requirement imposes that the computational, storage and bandwidth overheads must be kept at minimum. The eciency requirement is also closely related to the concept of amortized model, introduced by Gennaro et al. [90]. This model authorizes the user to run a one-time expensive preprocessing operation that prepares the function before its outsourcing. This preprocessing can be as costly as computing the function from scratch. However, after this stage, the preprocessing is amortized over an unlimited number of fast verications.
Denition of Veriable Computation
This section formally denes a Veriable Computation (VC) scheme. In a nutshell, a VC scheme is a two-party protocol in which a data owner outsources a computationally expensive function to a cloud server. Later on, the data owner submits some inputs of her choices to the server which is then required to evaluate the outsourced function on the requested inputs. The data owner nally veries that the output returned by the server actually corresponds to a correct evaluation of the outsourced function on the provided inputs. In the following, we identify the players in a VC protocol and describe their capabilities. Then, we present the system model of such a protocol.
Parties Involved
A VC scheme comprises the following players:
Data owner O: Data owner O outsources the computation of some (computationally demanding) function f belonging to a family of functions F to a cloud server S. Additionally, data owner O can provide cloud server S with some inputs x. The latter is required to compute y = f(x) and tries to convince data owner O that y is indeed f(x). O enjoys the capability to check that the result returned by S is correct. Cloud Server S: Often considered as potentially malicious, cloud server S is presumed to evaluate outsourced function f on requested input x. Cloud server S also produces a proof that the output f(x) is correct. Hence, we may refer to server S as the prover.
Adversary Model in Veriable Computation
A PVC scheme must fulll the basic security requirements of correctness and soundness. Succinctly, the correctness property states that if the server honestly evaluates the function based on the user’s input (i.e. correctly executes algorithm Compute), then the verier (who runs algorithm Verify) will always accept the server’s result. On the other hand, the soundness requirement captures the fact that a malicious server cannot make algorithm Verify (and thus the verier) accept a result that is not correctly computed via algorithm Compute.
Table of contents :
Acknowledgments
Abstract
List of Acronyms
List of Figures
List of Tables
Contents
Introduction
1 Topic of Research
1.1 Observations
1.2 Framing the Topic
2 Problem Statement
2.1 Questions raised by this thesis
2.2 Contributions
3 Organization
I Proofs of Storage
1 Characterization of Proofs of Storage
1.1 Introduction to Proofs of Storage
1.2 Denition of a Proof of Storage Protocol
1.2.1 Entities Involved in a POS Protocol
1.2.2 System Model
1.3 Requirements for a POS protocol
1.4 Security Model of a POS Scheme
1.4.1 Completeness
1.4.2 Soundness
1.5 State of the Art on Proofs of Storage
1.5.1 Deterministic Solutions
1.5.2 Probabilistic Solutions
1.5.3 Conclusion of the State of the Art
2 StealthGuard: Proofs of Retrievability with Hidden Watchdogs
2.1 Security Model of POR
2.1.1 Completeness
2.1.2 Soundness
2.2 StealthGuard
2.2.1 Intuition behind StealthGuard
2.2.2 StealthGuard Phases
2.2.3 Building Blocks
2.2.4 Description of the Entire Protocol
2.3 Security Analysis of our Protocol
2.3.1 Completeness
2.3.2 Soundness
2.4 Performance Analysis of StealthGuard
2.4.1 Discussion on Eciency
2.4.2 Example of Parameterization
2.4.3 Comparison with Related Work
2.4.4 Experimental Analysis
2.5 Conclusion
II Ecient Techniques for Veriable Computation
3 Charaterization of Veriable Computation
3.1 Introduction to Veriable Computation
3.2 Motivating Scenario
3.2.1 The Scenario
3.2.2 Requirements and Features for Veriable Computation Protocols
3.3 Denition of Veriable Computation
3.3.1 Parties Involved
3.3.2 System Model
3.4 Denition of Publicly Veriable Computation
3.4.1 Parties Involved in a PVC Protocol
3.4.2 System Model
3.5 Adversary Model in Veriable Computation
3.5.1 Correctness
3.5.2 Soundness
3.6 State of the Art in Veriable Computation
3.6.1 Non-Proof-based and Hardware-based Solutions
3.6.2 Proof-based General-Purpose Solutions
3.6.3 Proof-based Function-Specic Solutions
3.6.4 Conclusions of the State of the Art Analysis
4 Veriable Polynomial Evaluation
4.1 Introduction to Veriable Polynomial Evaluation
4.2 Protocol Overview
4.3 Building Blocks
4.3.1 Bilinear Pairings
4.3.2 D-Strong Die-Hellman Assumption
4.4 Protocol Description
4.4.1 Setup
4.4.2 Computation
4.4.3 Verication
4.5 Security Analysis
4.5.1 Correctness
4.5.2 Soundness
4.6 Performance Analysis
4.6.1 Storage
4.6.2 Communication
4.6.3 Computation
4.6.4 Comparison with Related Work
4.6.5 Experimental Results
4.7 Conclusion to Veriable Polynomial Evaluation
5 Veriable Matrix Multiplication
5.1 Introduction to Veriable Matrix Multiplication
5.2 Protocol Overview
5.3 Protocol Description
5.3.1 Setup
5.3.2 Computation
5.3.3 Verication
5.4 Security Analysis
5.4.1 Correctness
5.4.2 Soundness
5.5 Performance Analysis
5.5.1 Storage
5.5.2 Communication
5.5.3 Computation
5.5.4 Comparison with Related Work
5.5.5 Experimental Results
5.6 Conclusion to Veriable Matrix Multiplication
6 Veriable Conjunctive Keyword Search
6.1 Introduction to Veriable Conjunctive Keyword Search
6.2 Denition of Publicly Veriable Conjunctive Keyword Search
6.2.1 System Model
6.2.2 Denition of a Publicly Dynamic Veriable Conjunctive Keyword Search protocol
6.2.3 Adversary Model
6.3 Protocol Overview
6.4 Building Blocks
6.4.1 Cuckoo Hashing
6.4.2 Polynomial-based Accumulators and Applications
6.4.3 Binary Merkle Trees
6.5 Protocol Description
6.5.1 Setup
6.5.2 Search
6.5.3 Verication
6.5.4 Supporting Dynamic Data
6.6 Security Analysis
6.6.1 Correctness
6.6.2 Soundness
6.7 Performance Evaluation
6.7.1 Discussion on Eciency
6.7.2 Experimental Analysis
6.8 Conclusion to Veriable Keyword Search
III Accountability and Veriability
7 An Accountability Policy Language
7.1 Introduction
7.2 The Concepts of Accountability
7.2.1 Accountability Model
7.2.2 Accountability Actors and their Roles
7.2.3 Accountability and Policies
7.3 Motivating Scenario
7.4 Requirements for an Accountability Policy Language
7.4.1 Source of Accountability Obligations
7.4.2 Accountability Relationships and Obligations
7.4.3 Accountability Obligations
7.4.4 Policy Language Requirements
7.5 State of the Art on Policy Languages
7.5.1 Methodology
7.5.2 Survey of Existing Languages against the Language Requirements
7.6 A-PPL: a Policy Language for Accountability
7.6.1 Roles
7.6.2 Capturing Privacy Policies (R1)
7.6.3 Access Control Rules (R2)
7.6.4 Usage Control Rules (R3)
7.6.5 Data Retention (R4)
7.6.6 Reporting and Notication (R5)
7.6.7 Controlling Data Location (R6)
7.6.8 Auditability (R7)
7.6.9 Logging (R8)
7.7 A-PPLE: a policy engine for A-PPL
7.7.1 Description of A-PPLE
7.7.2 Operations of A-PPLE
7.7.3 Integration of our StealthGuard Prototype in A-PPLE
7.8 Example of A-PPL Statements with respect to our Healthcare Scenario
7.9 Conclusion
General Conclusions
Bibliography
