Description
Le problème SAT est un des piliers de l'informatique théorique et de la NP-Complétude. Sa résolution pratique a connu un réel essor ces dernières années. Les contributions en ce sens sont multiples et touchent un certain nombre de champs d'application. Les tentatives d'affaiblissements des primitives cryptographiques en font partie. Cet exposé rappellera les fondements du problème SAT, les limitations actuelles de sa résolution pratique (séquentielle et parallèle) et décrira les différentes approches qu'il est possible d'envisager pour modéliser une cryptanalyse par ce biais. Nous illustrerons ces principes avec une attaque pratique sur la seconde préimage d'une fonction de hachage cryptographique et sur un nombre de tours restreint, l'approche SAT constituant à ce jour et à notre connaissance la meilleure inversion pratique connue. Nous conclurons en donnant quelques pistes de recherche.
Prochains exposés
-
Encryption homomorphe sans bruit à l'aide de groupes
Orateur : Pierre Guillot - Ravel Technologies (dispo Université de Strasbourg, IRMA)
Je vais rappeler les travaux de Nuida et Ostrovski sur l'utilisation des groupes pour l'élaboration de schémas cryptographiques homomorphes. Je vais présenter nos travaux qui fournissent des encodages à la fois plus efficaces et plus généraux, et qui déterminent exactement quels groupes peuvent être utilisés. Puis je vais discuter GRAFHEN, un protocole qui utilise ces idées. Je dirai juste[…]-
Cryptography
-