Reutilizando 5 funções de hash independentes para análise linear

14

Em tabelas de hash que resolvem colisões por sondagem linear, para garantir desempenho esperado, é necessário e suficiente que a função de hash seja de uma família 5 independente. (Suficiência: "Sondagem linear com independência constante", Pagh et al. , Necessidade: "Sobre a independência k exigida pela sondagem linear e independência minima", Pătraşcu e Thorup )O(1)

Entendo que as famílias independentes 5 mais rapidamente conhecidas usam tabulação. Escolher uma função de uma família assim pode ser caro, então eu gostaria de minimizar o número de vezes que o faço, enquanto ainda evito ataques de complexidade algorítmica, conforme descrito em "Negação de serviço por ataques de complexidade algorítmica", de Crosby e Wallach . Estou menos preocupado com ataques de tempo (ou seja, adversários com cronômetros). Quais são as consequências de reutilizar a mesma função:

  1. Ao cultivar uma tabela de hash muito cheia?
  2. Ao reduzir uma tabela de hash que não está cheia o suficiente?
  3. Ao reconstruir uma tabela de hash com muitos bits "excluídos" definidos?
  4. Em tabelas de hash diferentes que podem conter algumas chaves em comum?k
  5. Em tabelas de hash diferentes que não contêm chaves em comum?k
ds.data-structures hash-function randomized-algorithms security jbapple
fonte
Se esta é uma pergunta sobre a prática ... uma abordagem pragmática plausível é usar uma função hash criptográfica, com um segredo aleatório incluído na entrada, em vez de usar um esquema baseado em tabulação. Depois, há menos pressão para reutilizar a mesma função de hash; você pode usar um segredo diferente para cada tabela de hash (e alterar o segredo e refazer tudo, ao diminuir / aumentar / reconstruir a tabela de hash).
DW
Eu acho que mesmo funções rápidas de hash criptográfico em entradas curtas como o SipHash-2-4 são bem lentas, mesmo quando comparadas a famílias independentes de 5 que usam polinômios.
jbapple

Respostas: