Hachage et identification

Le sujet de cet exposé est la longueur des valeurs de hachage dans les protocoles d’identification. Nous montrons que le modèle introduit par Stern et l’auteur à Crypto’94 est insuffisant, en ce qu’il se restreint implicitement aux attaquants “off-line”, qui ne se livrent à des calculs frauduleux qu’avant la procédure d’identification. Il s’ensuit que les théorèmes dérivés deviennent faux, quand on les applique à des valeurs de hachage trop courtes. Nous proposons un modèle plus réaliste, dans lequel des attaques off-line et on-line peuvent être perpétrées. De façon un peu surprenante, non seulement la “borne” (ou considérée comme telle) jusqu’ici admise d’environ 85 bits est encore valide, mais elle peut être fortement améliorée (entre 32 et 50 bits !) en faisant une hypothèse très acceptable, à savoir que l’identification doit se dérouler en un temps limité. En appliquant ce résultat à des schémas basés sur le logarithme discret, on atteint une certaine optimalité (identification quasi-instantanée, mémoire requise faible).