Séminaire LJK-Modèles et Algorithmes Déterministes: CASYS

 

Le Jeudi 15 Septembre 2016 à 14h00 en

 

Séminaire de Mme Cécile PIERROT

 

Salle 104 - Batiment IMAG- Génération d'aléa public et Bitcoin

 

Résumé:

 

La génération de nombres aléatoires publics et fiables est nécessaire à de nombreux protocoles de cryptographie. La première partie de cet exposé vise à présenter la notion d'"aléa public" et ne nécessite aucun prérequis. Bâtir une source publique d'aléa reste complexe et les propositions sont nombreuses. Parmi les différents moyens considérés, il a récemment été suggéré de s'appuyer sur l'imprédictabilité inhérente des chaines de blocs. C'est ici qu'interviennent les monnaies électroniques décentralisées, comme le Bitcoin, dont nous proposerons aussi une courte introduction. En effet l'entropie de la chaine publique sousjacente au Bitcoin a été utilisée, bien au delà de son rôle de registre monétaire, pour créer des lotteries, puis proposée par la suite pour d'autres applications variant de la rédaction de contrats intelligents à l'audit d'élections.

Nous montrerons comment un adversaire, même tenu par des contraintes financières étroites, et même s'il ne dispose que d'une puissance de calcul limitée, peut cependant manipuler ces nombres aléatoires. La génération de nombre publics aléatoires par ce moyen est donc à proscrire.
En passant, l'analyse de l'une des attaques possibles introduit une généralisation des mots de Dyck dont nous verrons ici une illustration, si nous avons le temps.

Il s'agit d'un travail commun avec Benjamin Wesolowski, doctorant à l'EPFL, Lausanne.