| Resumé |
Dans cette thèse, nous nous concentrons sur le problème du décodage du syndrome (SDP), sa généralisation, la cryptanalyse et son application à la conception de schémas de signature. Nous introduisons un nouveau problème, que nous appelons le problème de décodage de syndrome généralisé. Dans la partie cryptanalytique de la thèse, nous nous concentrons sur la cryptanalyse classique et quantique du problème de décodage de syndrome généralisé en utilisant les algorithmes de décodage par ensemble d'information. Plus précisément, nous calculons le temps d'exécution de trois algorithmes de (classiques) différents de ce type, que nous appelons les algorithmes de Prange, de Stern/Dumer et de Wagner. Les trois algorithmes sont adaptés pour résoudre des versions spécifiques du problème généralisé qui utilise le poids de Hamming, pris comme référence, et le poids de Lee, pris comme alternative au poids de Hamming. Nous comparons ensuite les temps d'exécution obtenus avec le temps d'exécution de l'algorithme hybride classique-quantique, obtenu en introduisant la recherche de Grover et l'amplification d'amplitude dans l'étape appropriée de l'algorithme de Wagner. Dans la partie de l'article consacrée à la conception de protocoles, nous modifions le protocole d'identification de Stern et le schéma de signature correspondant pour l'adapter au problème de décodage du syndrome généralisé nouvellement introduit. Pour conserver la propriété de divulgation nulle de connaissance du système, nous remplaçons finalement le problème de décodage de syndrome par celui du noyau permuté (PKP), pour lequel nous montrons que le problème SDP en moyenne se réduit au problème PKP en moyenne. Nous proposons ensuite différentes méthodes pour optimiser l'efficacité du système et fournissons des résultats numériques qui comparent l'efficacité de la construction originale et de notre nouveau système. Le résultat de ce travail est une analyse de la variante nouvellement introduite du problème de décodage de syndrome qui fournit une estimation de la complexité asymptotique du problème, ainsi que de la sécurité concrète du schéma basé sur ce problème. Les résultats indiquent que le choix approprié d'une fonction de poids introduit une version plus difficile du problème de décodage de syndrome et produit donc des protocoles plus efficaces basés sur ce problème. |