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.
|Title of host publication||Computer Security – ESORICS 2022 - 27th European Symposium on Research in Computer Security, Proceedings|
|Editors||Vijayalakshmi Atluri, Roberto Di Pietro, Christian D. Jensen, Weizhi Meng|
|Number of pages||21|
|Publication status||Published - 2022|
|Event||27th European Symposium on Research in Computer Security, ESORICS 2022 - Virtual, Online|
Duration: 26 Sep 2022 → 30 Sep 2022
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Conference||27th European Symposium on Research in Computer Security, ESORICS 2022|
|Period||26/09/22 → 30/09/22|
Bibliographical noteGreen Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care
Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.
- Hybrid homomorphic encryption
- Outsourced computation
- Verifiable computation