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.