Abstract
Gordon et al. (TCC 2015) systematically studied the security of Multi-client Verifiable Computation (MVC), in which a set of computationally-weak clients outsource the computation of a general function f over their private inputs to an untrusted server. They introduced the universally composable (UC) security of MVC and proposed a scheme achieving UC-security, where the protocol remains secure after arbitrarily composed with other UC-secure instances. However, the clients in their scheme have to undertake the heavy computation overhead caused by fully homomorphic encryption (FHE) and further, the plaintext size is linear to the function input size.
In this work, we propose a more efficient UC-secure multi-client privacy-preserving verifiable computation protocol, called MVOC, that sharply reduces amortized overheads for clients, in both semi-honest and malicious settings. In particular, our protocol achieves stronger outsourcability by outsourcing more computation to the server, so that it may be more friendly to those lightweight clients. More specifically, we revisit the definition of garbling scheme, and propose a novel garbled circuit protocol whose circuit randomness is non-interactively provided by multiple parties. We also realize the idea of hybrid homomorphic encryption, which makes the FHE plaintext size independent of the input size. We present the detailed proof and analyze the theoretical complexity of MVOC. We further implement our protocol and evaluate the performance, and the results show that, after adopting our new techniques, the computation and communication overheads during input phase can be decreased by 55.15%-68.05% and 62.55%-75% respectively.