MVOC: A Lighter Multi-Client Verifiable Outsourced Computation for Malicious Lightweight Clients

Gordon et al. systematically studied the Universally Composable (UC) security of Multi-client Verifiable Computation (MVC), in which a set of computationally-weak clients delegate the computation of a general function to an untrusted server based on their private inputs, and proposed a UC-secure scheme ensuring that the protocol remains secure even when arbitrarily composed with other UC-secure instances. However, this scheme imposed a significant computational overhead on clients due to the utilization of fully homomorphic encryption, and the plaintext size scaled linearly with function input size. In this work, we present MVOC, a more efficient UC-secure MVC protocol, that significantly reduces the amortized overhead for clients in both semi-honest and malicious settings, by delegating a larger portion of the computation to the server. We enable clients to verify the garbled circuit before entering the online phase, ensuring security against malicious clients without incurring heavy overhead of compiling a semi-honest protocol into a malicious one. We present the detailed proof and analyze the theoretical complexity of MVOC. Furthermore, we implement our protocol and evaluate the performance, and the results demonstrate that the computation and communication overheads during the input phase can be decreased by at least 95.55% and 87.17%, respectively.