Cryptology ePrint Archive: Report 2017/901

Stateful Multi-Client Verifiable Computation

Christian Cachin and Esha Ghosh and Dimitrios Papadopoulos and Björn Tackmann

Abstract: This paper develops a cryptographic protocol for outsourcing arbitrary stateful computation among multiple clients to an untrusted server, while guaranteeing integrity of the data. The clients communicate only with the server and store only a short authenticator to ensure that the server does not cheat.

Our contribution is two-fold. First, we extend the recent hash&prove scheme of Fiore et al. (CCS 2016) to stateful computations that support arbitrary updates by the untrusted server, in a way that can be verified by the clients. We use this scheme to generically instantiate authenticated data types. Second, we describe a protocol for multi-client verifiable computation based on an authenticated data type, and prove that it achieves a computational version of fork linearizability. This is the strongest guarantee that can be achieved in the setting where clients do not communicate directly; it ensures correctness and consistency of outputs seen by the clients individually.

Category / Keywords: cryptographic protocols / Byzantine emulation, verifiable computation, authenticated data types

Date: received 15 Sep 2017, last revised 23 Aug 2018

Contact author: bta at zurich ibm com

Available format(s): PDF | BibTeX Citation

Version: 20180823:152556 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]