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 9 Octobre 2012

Puzzle de Merkle dans le monde quantique

par Marc Kaplan (Equipe Information quantique du Département Informatique et réseaux au LTCI (CNRS, Telecom ParisTech))

En 1974, Ralph Merkle a proposé un schéma pour communiquer de façon sécurisée à travers un canal non-sécurisé. La sécurité de son protocole repose sur le fait suivant: les participants fournissent un effort calculatoire de l'ordre de N mais un espion ne peut pas apprendre leur communication sans fournir un effort de l'ordre de N2.

La sécurité du protocole de Merkle n'est plus valable face à un espion ayant accès à un ordinateur quantique. Brassard et Salvail ont montré que si les participants légitimes ont également accès à des ressources quantiques, alors il est possible de restaurer en partie la sécurité. Leur protocole nécessite un effort de l'ordre de N3/2 pour être brisé.

Nous présenterons deux nouveaux protocoles pour communiquer de manière sécurisée à travers un canal non sécurisé. Dans le premier, les participants légitimes ont accès à des ressources quantiques et un espion a besoin de fournir un effort de N5/3. Le second protocole est entièrement classique et offre une sécurité de l'ordre de N7/6 contre un adversaire qui a accès à des ressources quantiques.

Cet exposé ne nécessite pas de connaissance préalable de calcul quantique.

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