Integrity, consistency, and verification of remote computation

Abstract

With the advent of cloud computing, many clients have outsourced computation and data storage to remote servers. This has led to prominent concerns about the privacy of the data and computation placed outside the control of the clients. On the other hand, the integrity of the responses from the remote servers has been addressed in-depth only recently. Violations of correctness are potentially more dangerous, however, in the sense that the safety of a service is in danger and that the clients rely on the responses. Incidental computation errors as well as deliberate and sophisticated manipulations on the server side are nearly impossible to discover with today's technology. Over the last few years, there has been rising interest in technology to verify the results of a remote computation and to check the consistency of responses from a cloud service. These advances rely on recently introduced cryptographic techniques, including authenticated data types (ADT), probabilistically checkable proofs (PCPs), fully-homomorphic encryption (FHE), quadratic programs (QP), and more. With multiple clients accessing the remote service, a further dimension is added to the problem in the sense that clients isolated from each other need to guarantee that their verification operations relate to the same "version" of the server's computation state. This tutorial will survey the recent work in this area and provide a broad introduction to some of the key concepts underlying verifiable computation, towards single and multiple verifiers. The aim is to give a systematic survey of techniques in the realm of verifiable computation, remote data integrity, authenticated queries, and consistency verification. The approaches rely on methods from cryptography and from distributed computing. The presentation will introduce the necessary background techniques from these fields, describe key results, and illustrate how they ensure integrity in selected cases. The tutorial consists of three parts: 1. Verifiable computation; 2. Authenticated data types; 3. Distributed consistency enforcement. Copyright is held by the author/owner(s).