Lighter is Better: A Lighter Multi-client Verifiable Outsourced Computation with Hybrid Homomorphic Encryption

Xingkai Wang, Zhenfu Cao*, Zhen Liu, Kaitai Liang

*Corresponding author for this work

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

20 Downloads (Pure)


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.

Original languageEnglish
Title of host publicationComputer Security – ESORICS 2022 - 27th European Symposium on Research in Computer Security, Proceedings
EditorsVijayalakshmi Atluri, Roberto Di Pietro, Christian D. Jensen, Weizhi Meng
Number of pages21
ISBN (Print)978-3-031-17145-1
Publication statusPublished - 2022
Event27th European Symposium on Research in Computer Security, ESORICS 2022 - Virtual, Online
Duration: 26 Sept 202230 Sept 2022

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13555 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference27th European Symposium on Research in Computer Security, ESORICS 2022
CityVirtual, Online

Bibliographical note

Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project
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


Dive into the research topics of 'Lighter is Better: A Lighter Multi-client Verifiable Outsourced Computation with Hybrid Homomorphic Encryption'. Together they form a unique fingerprint.

Cite this