Verifiable Data and Computation Outsourcing to the Cloud

Recent years have witnessed the growing application of data and computation outsourcing to the cloud. One of the biggest challenges that hinder people adopting cloud computing is the security and privacy issue of the outsourced data and computation. In this thesis, we address the security challenge in three areas of cloud computing: verifiable cloud storage, verifiable file search, and verifiable computation outsourcing to the cloud.;VERIFIABLE CLOUD STORAGE. The problem is how a user can check the availability and integrity of the outsourced data. We propose two protocols to solve this problem. The first protocol establishes a generic and systematic way to construct a verifiable cloud storage protocol from any secure network coding protocol, which is the first generic protocol in the verifiable cloud storage area. The construction implies that we automatically have many such verifiable cloud storage protocols based on previous research on secure network coding. We also propose another protocol based on a classical string equality checking protocol in distributed computing. This protocol is simple both conceptually and technically compared with previous protocols. We implement both protocols and evaluate their performance. The experimental results validate the effectiveness and efficiency of the proposed protocols.;VERIFIABLE FILE SEARCH. The problem is how a user can search the files outsourced to the cloud verifiably. We propose two protocols to enable a user to verify whether a returned search answer from the cloud is indeed correct. The first protocol is based on two ideas. One is to separate all possible filenames into two finite sets. The other is to embed some secret information in the outsourced data to achieve verifiability. We also propose another protocol by modeling the file search problem as a traditional search problem. By combining hashing and a semantic authentication tree, we solve the verifiable search problem elegantly. The proposed two protocols excel each other in different performance indicators. Theoretical and experimental results validate the effectiveness and efficiency of our protocols.;VERIFIABLE COMPUTATIONAL OUTSOURCING. The problem is how a client can offload some computation-intensive task to the cloud in a privacy-preserving and verifiable way. The challenging point is that the cloud cannot obtain meaningful knowledge about the outsourced data, and that the result of the computation can be verified by the user. We focus on some fundamental computation tasks, e.g. linear programming, linear equation, and linear regression computation outsourcing, which are common tools in engineering problem modeling and solving. We propose protocols for outsourcing these problems in a privacy-preserving, efficient, and verifiable way. By trade-offing reasonable security guarantee, the proposed protocols enjoy high efficiency. We can also trade efficiency for security, leading to less efficient yet more secure protocols. Theoretical and experimental analysis validate the effectiveness and efficiency of the proposed protocols.;By investigating the above three problems as a case study, this thesis solved some important security challenges in cloud computing on one hand; on the other hand, this thesis also identified potential security requirements of practical applications, proposed useful frameworks and presented useful ideas in addressing real-world problems. We hope these contributions could also shed insights on addressing other security challenges in cloud computing.