The 44th IPP Symposium

Delegation in the Cloud

Feng-Hao Liu, Brown University

Delegation of computing becomes a fast growing scenario in the emergence of cloud computing - organizations or individuals (referred to as the delegator), instead of maintaining their own system, may outsource their computational tasks to specialized providers (e.g., Amazon) or anonymous users on the Internet (e.g., SETI@Home) (referred to as the cloud). In order to ensure the cloud perform the computation correctly, we like the cloud to provide a proof to the delegator, which allows the verification time significantly less than the computation time. Recently, there have been several results to this question, considering delegating general or specific functionalities, and verifying the correctness in time almost linear in the data size.

We take a forward step by considering a scenario where the data are so huge that the delegator wants to delegate them to the cloud as well. Once the data are delegated, the delegator only needs to keep a short certificate, and then can verify the computation in time sub-linear in the data size. We call this task *memory delegation.* A natural example is our email system: users store their mails in the mail server (Gmail), and they can request some computations on the mails, such as search, delete, label, etc. Another natural scenario is *streaming delegation* where a stream of huge data comes by, and the delegator, who cannot store them all, delegates the task to the cloud. Later on, the delegator may ask for some computation on the data, and a proof of correctness from the cloud.

In this talk, I will present our models for these two scenarios and our solutions. Our schemes are non-interactive, where the delegator sends one message and the cloud replies the answer and a proof, for delegating "uniform-NC" computations, (informally, computations that can be efficiently parallelized), and four-round protocols for delegating general polynomial-time computations. In all the cases, the delegator can verify the answer in time poly-logarithmic in the size of the memory (or the stream), with the help a short certificate of the memory (or the stream). This is a joint work with Kai-Min Chung (Cornell), Yael Kalai (MSR), and Ran Raz (Weizmann.

Feng-Hao is a PhD student in the CS department working with Anna Lysyanskaya. He is interested in foundations of cryptography and their applications. Specific topics are hardness amplification, delegation of computation, and cryptography under different physical attacks. Before coming to Brown, he received his bachelor's degree from the Department of Electrical Engineering, National Taiwan University.