Reutilización de 5 funciones hash independientes para sondeo lineal

14

En las tablas hash que resuelven colisiones mediante sondeo lineal, para garantizar el rendimiento esperado de , es necesario y suficiente que la función hash sea de una familia independiente de 5. (Suficiencia: "Sondeo lineal con independencia constante", Pagh et al. , Necesidad: "Sobre la independencia k requerida por el sondeo lineal y la independencia mínima", Pătraşcu y Thorup )O(1)

Entiendo que las familias independientes más rápidas que se conocen usan la tabulación. Elegir una función de una familia así puede ser costoso, por lo que me gustaría minimizar la cantidad de veces que lo hago mientras evito los ataques de complejidad algorítmica como se describe en "Denegación de servicio de Crosby y Wallach a través de ataques de complejidad algorítmica" . Estoy menos preocupado por los ataques de tiempo (es decir, adversarios con cronómetros). ¿Cuáles son las consecuencias de reutilizar la misma función?

  1. ¿Al cultivar una tabla hash que está demasiado llena?
  2. ¿Al reducir una tabla hash que no está lo suficientemente llena?
  3. Al reconstruir una tabla hash que tiene demasiados bits "eliminados" establecidos?
  4. ¿En diferentes tablas hash que pueden contener algunas claves en común?k
  5. ¿En diferentes tablas hash que no contienen claves en común?k
ds.data-structures hash-function randomized-algorithms security jbapple
fuente
Si esta es una pregunta sobre la práctica ... un enfoque pragmático plausible es usar una función hash criptográfica, con un secreto aleatorio incluido en la entrada, en lugar de usar un esquema basado en la tabulación. Entonces hay menos presión para reutilizar la misma función hash; puede usar un secreto diferente para cada tabla hash (y cambiar el secreto y volver a mostrar todo, al reducir / aumentar / reconstruir la tabla hash).
DW
Creo que incluso las funciones hash criptográficas rápidas en entradas cortas como SipHash-2-4 son bastante lentas en comparación incluso en comparación con las familias independientes de 5 que usan polinomios.
jbapple

Respuestas: