Exploration de l'approche multi-dimensionnelle en cryptographie fondée sur les codes correcteurs d'erreurs

Discipline

Informatique

Classification

Informatique

Mots-clés libres

Cryptographie, Mathématiques appliquées, Théorie des codes, Informatique

Mots-clés

Cryptographie post-quantique,

Codes correcteurs d'erreurs (théorie de l'information),

Systèmes informatiques -- Mesures de sûreté

La cryptographie fondée sur les codes est une famille féconde d'algorithmes post-quantiques. Sa sécurité repose principalement sur le problème de décoder des mots bruités dans un code aléatoire, qui est réputé difficile pour un ordinateur classique ainsi que pour un ordinateur quantique. Un des défis de la cryptographie post-quantique est sa large taille de clé publique et de message par rapport à la cryptographie classique. Pour remédier à ce problème, on peut considérer des objets avec une structure cyclique, prenant un espace réduit en mémoire. Cette approche implique cependant de ne plus reposer sur une instance générique du problème de décodage, ce qui peut créer des vulnérabilités. Dans cette thèse, nous explorons une approche multi-dimensionnelle pour réduire la taille des schémas, tout en ayant plus de sécurité que l'ajout de structure cyclique. Cette récente approche consiste à envoyer des erreurs multiples de même support, permettant d'augmenter la capacité de décodage des codes et donc de diminuer la taille des paramètres. Bien entendu, le problème difficile dans la preuve de sécurité doit être adapté au cas multi-dimensionnel, mais nous pensons que cette variante est moins risquée que la variante cyclique. Nous présentons dans cette thèse deux nouveaux schémas de chiffrement et un nouveau schéma de signature fondés sur cette approche multi-dimensionnelle. Ils sont plus performants que les propositions existantes sans structure. Nous donnons aussi une application de l'approche multi-dimensionnelle au chiffrement homomorphe fondé sur des codes idéaux aléatoires.