Paper 2020/132

Boosting Verifiable Computation on Encrypted Data

Dario Fiore, Anca Nitulescu, and David Pointcheval

Abstract

We consider the setting in which an untrusted server stores a collection of data and is asked to compute a function over it. In this scenario, we aim for solutions where the untrusted server does not learn information about the data and is prevented from cheating. This problem is addressed by verifiable and private delegation of computation, proposed by Gennaro, Gentry and Parno (CRYPTO’10), a notion that is close to both the active areas of homomorphic encryption and verifiable computation (VC). However, in spite of the efficiency advances in the respective areas, VC protocols that guarantee privacy of the inputs are still expensive. The only exception is a protocol by Fiore, Gennaro and Pastro (CCS’14) that supports arithmetic circuits of degree at most 2. In this paper we propose new efficient protocols for VC on encrypted data that improve over the state of the art solution of Fiore et al. in multiple aspects. First, we can support computations of degree higher than 2. Second, we achieve public delegatability and public verifiability whereas Fiore et al. need the same secret key to encode inputs and verify outputs. Third, we achieve a new property that guarantees that verifiers can be convinced about the correctness of the outputs without learning information on the inputs. The key tool to obtain our new protocols is a new SNARK that can efficiently handle computations over a quotient polynomial ring, such as the one used by Ring-LWE somewhat homomorphic encryption schemes. This SNARK in turn relies on a new commit-and-prove SNARK for proving evaluations on the same point of several committed polynomials. We propose a construction of this scheme under an extractability assumption over bilinear groups in the random oracle model.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in Pkc 2020
Keywords
Verifiable Computationzk-SNARKsPolynomial Commitments
Contact author(s)
anca nitulescu @ cosmian com
dario fiore @ imdea org
david pointcheval @ ens fr
History
2020-02-10: received
Short URL
https://ia.cr/2020/132
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/132,
      author = {Dario Fiore and Anca Nitulescu and David Pointcheval},
      title = {Boosting Verifiable Computation on Encrypted Data},
      howpublished = {Cryptology ePrint Archive, Paper 2020/132},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/132}},
      url = {https://eprint.iacr.org/2020/132}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.