On the Verification of Computation and Data Retrievability

The cloud model offers many useful services such as storage and computing solutions that enrich our daily lives. However, there is a restriction in using the cloud's optimal potential since the client relies on trusting the cloud completely. This blind faith can easily be exploited by the cloud by lying about computational results or deleting data; making verification of results a desirable property to obtain a level of assurance while relaxing the trust assumption.

Publicly verifiable computation (PVC) enables a computationally-limited client to outsource computations to an untrusted server and to verify correctness of the returned results. Servers providing such a service may be rewarded per computation, providing an incentive to cheat by returning malformed results rather than devoting time and resources to compute a valid result. In this thesis, we extend a previous approach using attribute-based encryption (ABE) to enable a broader system model for PVC such that servers may compute multiple functions and if found cheating, are revoked from the system. We show that different types of ABE accommodate different system models and ultimately show that dual-policy ABE unifies all ABE based PVC models into a hybrid model which can flexibly switch between the models at the cost of a single setup.

Proofs of retrievability (PoR) enable a client to outsource data to an untrusted server and allow the client to request a proof that the data stored can be retrieved, which the client can verify. We construct a somewhat practical scheme that enables the client to request proofs of retrievability of multiple different-sized files with a single request.
This is achieved by using homomorphic properties to aggregate a proof into a small value. Furthermore, using combinatorial and statistical tools we derive strategies obtaining an assurance whether the server retains enough information to deliver the original data.