PICSI

Algorithme à clé publique: SD (codes correcteurs d'erreurs)

Le schéma SD, dû à Stern [1], est un protocole d'authentification de type zero-knowledge à multiples passes. Il tire son du nom du problème sur lequel sa sécurité est fondée : Syndrome Decoding. Ce problème est central dans la théorie des codes correcteurs d'erreurs, et a été utilisé la première fois à des fins cryptographiques en 1978 par McEliece [2]. Le schéma de chiffrement qui porte son nom utilise les codes dits de Goppa, tandis que SD utilise des codes "aléatoires".

Un attrait important de la théorie des codes correcteurs d'erreurs est que les opérations élémentaires sont extrêmement rapides et faciles à implémenter. Elles se réduisent en effet pour l'essentiel à des multiplications et additions dans de très petits corps finis (typiquement le corps à deux éléments). En revanche, les matrices et vecteurs qu'elle manipule sont généralement de grande taille, ce qui, dans des applications cryptographiques, aboutit à des clés publiques de très grande taille également (typiquement 1 Mbit). Cependant, des recherches très récentes visent à corriger ce défaut [3].

Dans le schéma SD, la clé secrète est un mot binaire de poids très faible w et la clé publique est le syndrome de ce mot dans un code choisi aléatoirement. En d'autres termes, si l'on appelle H une matrice binaire (k-n) choisie au hasard et s la clé secrète de n bits, alors la clé publique v est le mot de k bits obtenu en multipliant H par s. Des valeurs typiques sont : n = 1024, k = 512 et w = 110. Un protocole en trois passes permet au prouveur de montrer sa connaissance de s sans rien en révéler. Cependant, comme un imposteur dispose d'une stratégie pour satisfaire ce protocole avec deux chances sur trois, on réduit sa chance de manière exponentielle en itérant le protocole plusieurs fois.





[1] J. Stern. A new identification scheme based on syndrome decoding. In Advances in Cryptology - Crypto‘93, LNCS 773, pages 13-21, Springer-Verlag, 1993.

[2] R. J. McEliece. A public-key cryptosystem based on algebraic coding theory. DSN Prog. Rep., Jet Prop. Lab., California Inst. Technol., Pasadena, CA, pages 114-116, January 1978.

[3] P. Gaborit. Shorter keys for the McEliece cryptosystem. Proc. of WCC 2005.