Réutilisation de 5 fonctions de hachage indépendantes pour le sondage linéaire

14

Dans les tables de hachage qui résolvent les collisions par sondage linéaire, afin d'assurer les performances attendues de , il est à la fois nécessaire et suffisant que la fonction de hachage provienne d'une famille à 5 indépendants. (Suffisance: "Sondage linéaire avec indépendance constante", Pagh et al. , Nécessité: "Sur la k-indépendance requise par le sondage linéaire et l'indépendance Minwise", Pătraşcu et Thorup )O(1)

Je crois comprendre que les familles indépendantes connues les plus rapides utilisent la tabulation. Choisir une fonction d'une telle famille peut coûter cher, donc je voudrais minimiser le nombre de fois que je le fais tout en empêchant les attaques de complexité algorithmique comme décrit dans Crosby et Wallach "Denial of Service via Algorithmic Complexity Attacks" . Je suis moins préoccupé par le timing des attaques (c'est-à-dire des adversaires avec chronomètres). Quelles sont les conséquences de la réutilisation de la même fonction:

  1. Lors de la croissance d'une table de hachage trop pleine?
  2. Lorsque vous réduisez une table de hachage qui n'est pas suffisamment pleine?
  3. Lors de la reconstruction d'une table de hachage avec trop de bits "supprimés" définis?
  4. Dans différentes tables de hachage qui peuvent contenir certaines clés en commun?k
  5. Dans tables de hachage différentes qui ne contiennent aucune clé en commun?k
ds.data-structures hash-function randomized-algorithms security jbapple
la source
S'il s'agit d'une question de pratique ... une approche pragmatique plausible consiste à utiliser une fonction de hachage cryptographique, avec un secret aléatoire inclus dans l'entrée, au lieu d'utiliser un schéma basé sur la tabulation. Ensuite, il y a moins de pression pour réutiliser la même fonction de hachage; vous pouvez utiliser un secret différent pour chaque table de hachage (et changer le secret et tout ressasser, lors de la réduction / croissance / reconstruction de la table de hachage).
DW
Je pense que même les fonctions de hachage cryptographique rapides sur des entrées courtes comme SipHash-2-4 sont assez lentes par rapport aux familles indépendantes utilisant des polynômes.
jbapple

Réponses: