Réductions boîte-noires : notions et quelques résultats d'impossibilité

par Chloé Hébant (Master Cryptis), Neals Fournaise (Master Cryptis)

mardi 23 févr. 2016, 15:30 → 16:30 Europe/Paris

P09 (Faculté des sciences et Techniques)

Une des questions majeures en crypto est de savoir s’il est possible de construire une primitive à partir d’une autre (e.g est ce possible de construire un schéma de signature numérique à partir d'un générateur pseudo-aléatoire?). La plupart de telles réductions est de type boîte-noire au sens de la complexité. Hebant Chloé et Neals Fournaise traitent la question intéressante de l’impossibilité de faire des réductions boîte-noires entre certaines primitives. Ils présent ensuites quelques preuves de « séparations » entre les primitives.

Paper Limits on the Provable Consequences of One-way Functions Notions of Reducibility between Cryptographic Primitives