Calcul vérifiable et vérification biométrique
Institution:
Sorbonne universitéDisciplines:
Directors:
Abstract EN:
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.
Abstract FR:
Cette thèse s'articule autour de la notion de calcul vérifiable, dont le but est de joindre au résultat d'un calcul une preuve que ce calcul est correct. De plus, vérifier la preuve du calcul doit être plus efficace que de l'exécuter. Il devient alors possible de déléguer des calculs à une entité sans hypothèse de confiance. La première partie de la thèse présente les éléments nécessaires à la compréhension des protocoles de calcul vérifiable et explicite les constructions des différents systèmes à l'état de l'art. Les nombreux systèmes de calcul vérifiable proposés depuis 2012 ont permis de s'approcher d'une utilisation pratique du calcul vérifiable. Même s'il existe des protocoles très efficaces adaptés à un type particulier de calcul, il semble nécessaire au contraire de considérer des protocoles capables de vérifier une grande classe de problèmes pour ne pas avoir à accumuler des preuves pour chaque partie d'un problème complexe. Dans la seconde partie de cette thèse, nous présentons un protocole de calcul vérifiable non-interactif qui s'appuie sur la composition de preuves pour obtenir un prouveur plus efficace, sans que le système obtenu ne perde en expressivité. Certaines des constructions de systèmes de calcul vérifiable permettent d'obtenir une preuve de calcul à divulgation nulle de connaissances avec un effort de calcul supplémentaire négligeable pour le prouveur. Pour finir, nous présentons deux applications qui utilisent cette propriété pour définir de nouvelles primitives, la première permettant de modifier un document signé tout en gardant une forme d’authenticité, la seconde permettant de réaliser une authentification biométrique respectant la vie privée.