This thesis deals with the notion of verifiable computation, which aims at adding a proof of correctness to the result of a computation. Besides, verifying the proof should be more efficient than executing it. Verifiable computation protocols pave the way for delegation of computations to an untrusted party. The first part of this thesis introduces the background required to understand the most important verifiable computation protocols and describes their construction.
Many protocols have been proposed since 2012 and some are nearly practical, but the prover often lacks efficiency. Even though several specialized protocols are very efficient, it seems more appropriate to consider protocols that can verify a large class of computations, in order to avoid the multiplications of proofs for each sub-computation. In the second part of this thesis, we leverage proof composition to obtain a non-interactive verifiable computation protocol with a more efficient prover while keeping the expressiveness of the scheme.
Some of the existing verifiable computation systems reach additional properties and provide zero-knowledge for the proof with little overhead for the prover. We propose two applications that leverage this property to design new primitives. This first one enables to modify a signed document while keeping a form of authenticity. The second one allows for a privacy-preserving biometric authentication.
