Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 23 Janvier 2001

Les "Gap-Problems", une nouvelle classe de problèmes et leur implication dans la sécurité des protocoles cryptographiques

par David Pointcheval (ENS Ulm)

Travail commun avec Tatsuaki Okamoto (NTT, Japon)

De nombreux protocoles cryptographiques sans faille "apparente" sont pourtant exclus de preuves formelles de sécurité. Après une étude approfondie, nous avons remarqué que nombre de blocages sont liés aux hypothèses calculatoires que l'on admet.

Ainsi, suite à la définition de nouveaux problèmes calculatoires, et donc à de nouvelles hypothèses, nous avons ainsi pu prouver la sécurité de plusieurs protocoles très efficaces (des schémas de chiffrement asymétrique, de mise en accord de clé, mais aussi la signature indéniable de Chaum datant de 1990).

Ces nouveaux problèmes constituent en fait une nouvelle classe, au même titre que les problèmes calculatoires (ex: la factorisation, la racine carrée modulaire, etc) ou les problèmes décisionnels (ex: la résiduosité quadratique, etc). En fait, un "gap-problem" est la résolution d'un problème calculatoire avec accès à un oracle qui résout un problème décisionnel (ex: résoudre le problème de la racine carrée modulaire avec un accès à un oracle qui répond si un nombre est un résidu quadratique ou non).

Une analyse a été menée pour relier la difficulté du "Gap-Problem" aux problèmes calculatoires et décisionnels sous-jacents. Le cas particulier des problèmes uniformément auto-réductibles, très utilisés en cryptographie (logarithme discret, exponentiation modulaire, etc), a été plus particulièrement étudié, et conduit à des résultats très simples.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr