Etude d'un cas d'optimisation des modes opératoires en arbre pour des fonctions de hachage parallèles

English

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

30/03/2017 - 09:30 Mr Kévin Atighehchi

Nous nous intéressons à des modes opératoires parallèles pour une fonction de hachage supposée être à taux unitaire, avec un état interne de la même taille qu'un bloc du message. Calculatoirement, une telle fonction a la caractéristique intéressante de ne nécessiter que $x$ appels à la primitive sous-jacente pour traiter un message de $x$ blocs. Afin de concrétiser une telle fonction, nous nous utilisons une variante de la construction de Merkle-Damgård (Coron et al., CRYPTO 2005). Nous construisons alors une fonction de hachage s'appuyant sur cette dernière au moyen d'un arbre ayant toutes ses feuilles à la même profondeur. Dans ce travail, nous caractérisons les structures arborescentes à utiliser pour réduire au mieux le temps d'exécution de la fonction qui en résulte. Ensuite, sans affecter ce temps d'exécution, nous montrons comment réduire le nombre de processeurs. En particulier, nous cherchons à libérer les processeurs le plus rapidement possible à chaque étape du calcul. Enfin, nous donnons un exemple de fonction de hachage utilisant ces optimisations et les résultats de Bertoni et al. (IJIS 2014), qui assure son indifférentiabilité d'une fonction de hachage idéale.