A1 Refereed original research article in a scientific journal
MVOC: A Lighter Multi-Client Verifiable Outsourced Computation for Malicious Lightweight Clients
Authors: Wang, Xingkai; Cao, Zhenfu; Liu, Zhen; Liang, Kaitai
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Publication year: 2025
Journal: IEEE Transactions on Dependable and Secure Computing
Volume: 22
Issue: 2
First page : 1640
Last page: 1654
ISSN: 1545-5971
eISSN: 2160-9209
DOI: https://doi.org/10.1109/TDSC.2024.3449770
Publication's open availability at the time of reporting: No Open Access
Publication channel's open availability : Partially Open Access publication channel
Web address : https://doi.org/10.1109/tdsc.2024.3449770
Abstract
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.
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.
UTU Research Portal