Post-quantum zero-knowledge proofs using homomorphic bit commitment

Abstract

Avec la montée en puissance des ordinateurs quantiques, il est plus important que jamais de démontrer que les protocoles cryptographiques sont sécuritaires contre des adversaires quantiques. De plus, l'objectif de tout cryptographe est d’assouplir certaines hypothèses, en particulier celles qui restreignent la capacité de l’adversaire à effectuer de longs calculs. Dans cette thèse, un système multi-parties est utilisé pour créer deux preuves Zéro-Knowledge (ZK), celles-ci opèrent en temps polynomial et sont sécurisées. De plus, elles n’ont aucune restriction calculatoire pour aucune partie, même pour les adversaires qui partagent une intrication quantique. Une preuve ZK permet à une partie de prouver à une autre partie d’un fait sans révéler aucune connaissance autre que la véracité du fait. Par exemple, une telle preuve pourrait être utilisée pour permettre à un client de prouver son identité à un guichet bancaire sans donner des renseignements confidentiels tel que son numéro d'identification personnel. Un des principaux outils utilisés lors d’une preuve ZK est le schéma de mise en gage. Celui-ci est essentiellement un outil numérique permettant à un expéditeur de sceller un message dans un coffre-fort et de l’envoyer à un destinataire. Ensuite, quand l'expéditeur veut que le destinataire lise le message, la clé du coffre fort lui est envoyée. Ceci permet au message de rester inconnu du receveur jusqu'à ce qu’il reçoive la clé de l'expéditeur. De plus, l'expéditeur ne peut pas changer le message une fois le coffre-fort envoyé. Au cours de cette thèse, les propriétés homomorphiques d’un schéma multi-parties de mise en gage sont utilisées pour permettre au destinataire d’effectuer des opérations sur le gage. Ceci donne ainsi des preuves ZK pour deux problèmes NP-complets, les problèmes de la somme de sous-ensembles et 3-SAT