Cryptology ePrint Archive: Report 2020/1526

Flexible and Efficient Verifiable Computation on Encrypted Data

Alexandre Bois and Ignacio Cascudo and Dario Fiore and Dongwoo Kim

Abstract: We consider the problem of verifiable and private delegation of computation [Gennaro et al. CRYPTO'10] in which a client stores private data on an untrusted server and asks the server to compute functions over this data. In this scenario we aim to achieve three main properties: the server should not learn information on inputs and outputs of the computation (privacy), the server cannot return wrong results without being caught (integrity), and the client can verify the correctness of the outputs faster than running the computation (efficiency). A known paradigm to solve this problem is to use a (non-private) verifiable computation (VC) to prove correctness of a homomorphic encryption (HE) evaluation on the ciphertexts. Despite the research advances in obtaining efficient VC and HE, using these two primitives together in this paradigm is concretely expensive. Recent work [Fiore et al. CCS'14, PKC'20] addressed this problem by designing specialized VC solutions that however require the HE scheme to work with very specific parameters; notably HE ciphertexts must be over $\mathbb{Z}_q$ for a large prime $q$.

In this work we propose a new solution that allows a flexible choice of HE parameters, while staying modular (based on the paradigm combining VC and HE) and efficient (the VC and the HE schemes are both executed at their best efficiency). At the core of our new protocol are new homomorphic hash functions for Galois rings. As an additional contribution we extend our results to support non-deterministic computations on encrypted data and an additional privacy property by which verifiers do not learn information on the inputs of the computation.

Category / Keywords: cryptographic protocols / verifiable computation, homomorphic encryption, homomorphic hash functions

Original Publication (with major differences): IACR-PKC-2021

Date: received 4 Dec 2020, last revised 16 Mar 2021

Contact author: dario fiore at imdea org,alexandre bois-verdiere@student ecp fr,ignacio cascudo@imdea org,Dongwoo Kim@wdc com

Available format(s): PDF | BibTeX Citation

Version: 20210316:082623 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]