Paper 2022/646

Faster Non-interactive Verifiable Computing

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

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.

Available format(s)
-- withdrawn --
Cryptographic protocols
Publication info
Contact author(s)
pascal lafourcade @ uca fr
gael marcadet @ uca fr
leo robert @ uca fr
2022-10-17: withdrawn
2022-05-25: received
See all versions
Short URL
Creative Commons Attribution
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.