Paper 2020/1526

Flexible and Efficient Verifiable Computation on Encrypted Data

Alexandre Bois, Ignacio Cascudo, 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in PKC 2021
Keywords
verifiable computationhomomorphic encryptionhomomorphic hash functions
Contact author(s)
dario fiore @ imdea org
alexandre bois-verdiere @ student ecp fr
ignacio cascudo @ imdea org
Dongwoo Kim @ wdc com
History
2021-03-16: revised
2020-12-08: received
See all versions
Short URL
https://ia.cr/2020/1526
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1526,
      author = {Alexandre Bois and Ignacio Cascudo and Dario Fiore and Dongwoo Kim},
      title = {Flexible and Efficient Verifiable Computation on Encrypted Data},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1526},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1526}},
      url = {https://eprint.iacr.org/2020/1526}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.