Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Hachage universel
Résumé
En mathématiques et en informatique, le hachage universel, en anglais universal hashing, (dans un algorithme probabiliste ou un bloc de données) est une méthode qui consiste à sélectionner aléatoirement une fonction de hachage dans une famille de fonctions de hachages qui ont certaines propriétés mathématiques. Cela permet de minimiser la probabilité de collision de hachage. Plusieurs familles de fonctions de hachages sont connues (pour hacher des entiers, des chaînes de caractères ou des vecteurs), et leur calcul est souvent très efficace. Le hachage universel a de nombreux usages en informatique, par exemple dans l’implémentation des tables de hachage, les algorithmes probabilistes et le chiffrement de données.
Supposons que nous désirions associer des clés provenant de l'univers à des fragments binaires (indexés ). L'algorithme devra gérer des ensembles de données à partir des clés, qui n'est pas connu à l'avance. Habituellement le but du hachage est de minimiser le nombre de collisions (clés de qui ont la même image par la fonction). Une fonction de hachage déterministe ne peut pas offrir la garantie contre la création intentionnelle de collision si la taille de est plus grande que la taille de par l'adversaire pour choisir de telle sorte qu'il soit l'antécédent d'un fragment. Cela donne un ensemble de clés qui donnent toutes le même hash, rendant le hachage virtuellement inutile.
De plus une fonction de hachage déterministe ne se prête pas au rehachage qui peut être nécessaire si un trop grand nombre de collisions a été constaté.
La solution à ces problèmes est de choisir la fonction de hachage de manière aléatoire à partir d'une famille de fonctions de hachage. Une famille de fonctions est appelée famille universelle si .
En d'autres mots, deux clés prises au hasard dans l'univers ont une probabilité au plus de de donner une collision quand la fonction est tirée aléatoirement de . C'est la probabilité à laquelle on s'attendrait si la fonction de hachage attribuait un hash de manière aléatoire à chaque clé.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.