Paper 2022/646

Faster Non-interactive Verifiable Computing

Pascal Lafourcade, Université Clermont-Auvergne
Gael Marcadet, Université Clermont-Auvergne
Léo Robert, Université Clermont-Auvergne
Abstract

In 1986, A.Yao introduced the notion of garbled circuits, designed to verify the correctness of computations performed on an untrusted server. However, correctness is guaranteed for only one input, meaning that a new garbled circuit must be created for each new input. To address this drawback, in 2010 Gennaro et al. performed the evaluation of the garbled circuit homomorphically using Fully Homomorphic Encryption scheme, allowing to reuse the same garbled circuit for new inputs. Their solution requires to encrypt the garbled circuit at every new input. In this paper, we propose a verifiable-computation scheme allowing to verify the correctness of computations performed by an untrusted server for multiple inputs, where the garbled circuit is homomorphically encrypted only once. Hence, we have a faster scheme comparing to Gennaro’s solution, since for each new input, we reduce the computations by the size of the circuit representing the function to be computed, for the same security level. The key point to obtain this speed-up is to rely on Multi-Key Homomorphic Encryption (MKHE) and then to encrypt only once the garbled circuit.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Contact author(s)
pascal lafourcade @ uca fr
gael marcadet @ uca fr
leo robert @ uca fr
History
2022-05-28: approved
2022-05-25: received
See all versions
Short URL
https://ia.cr/2022/646
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/646,
      author = {Pascal Lafourcade and Gael Marcadet and Léo Robert},
      title = {Faster Non-interactive Verifiable Computing},
      howpublished = {Cryptology ePrint Archive, Paper 2022/646},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/646}},
      url = {https://eprint.iacr.org/2022/646}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.