Cryptology ePrint Archive: Report 2015/142

Multi-Client Verifiable Computation with Stronger Security Guarantees

S. Dov Gordon and Jonathan Katz and Feng-Hao Liu and Elaine Shi and Hong-Sheng Zhou

Abstract: Choi et al. (TCC 2013) introduced the notion of multi-client verifiable computation (MVC) in which a set of clients outsource to an untrusted server the computation of a function f over their collective inputs in a sequence of time periods. In that work, the authors defined and realized multi-client verifiable computation satisfying soundness against a malicious server and privacy against the semi-honest corruption of a single client. Very recently, Goldwasser et al. (Eurocrypt 2014) provided an alternative solution relying on multi-input functional encryption.

Here we conduct a systematic study of MVC, with the goal of satisfying stronger security requirements. We begin by introducing a simulation-based notion of security that provides a unified way of defining soundness and privacy, and automatically captures several attacks not addressed in previous work. We then explore the feasibility of achieving this notion of security. Assuming no collusion between the server and the clients, we demonstrate a protocol for multi-client verifiable computation that achieves strong security in several respects. When server-client collusion is possible, we show (somewhat surprisingly) that simulation-based security cannot be achieved in general, even assuming semi-honest behavior.

Category / Keywords: cryptographic protocols / Verifiable Computation, Attribute-based Encrpytion, Functional Encryption

Original Publication (with minor differences): IACR-TCC-2015

Date: received 20 Feb 2015

Contact author: fenghao at cs umd edu

Available format(s): PDF | BibTeX Citation

Version: 20150227:205806 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]