Hash quase universal de cordas no espaço

9

Aqui estão duas famílias de funções de hash nas strings :x=x0x1x2xm

  1. Para prime e , para a \ in \ mathbb {Z} _p . Dietzfelbinger et al. mostrado em "Funções de hash polinomiais são confiáveis" que \ forall x \ neq y, P_a (h ^ 1_a (x) = h ^ 1_a (y)) \ leq m / p .x iZ p h 1 a ( x ) = a i x i mod p a Z px y , P a ( h 1 a ( x ) = h 1 a ( y ) ) m / ppxiZpha1(x)=aiximodpaZpxy,Pa(ha1(x)=ha1(y))m/p

  2. Para xiZ2b , ha=a0a1a2am+12(x)=(a0+ai+1ximod22b)÷2b para aiZ22b . Lemire e Kaser mostraram em "O hashing de cordas fortemente universal é rápido" que essa família é independente de dois. Isso implica que xy,Pa(ha2(x)=ha2(y))=2b

h1 usa apenas lgp bits de espaço e bits de aleatoriedade, enquanto h2 usa 2bm+2b bits de espaço e bits de aleatoriedade. Por outro lado, h2 opera sobre Z22b , o que é rápido em computadores reais.

Gostaria de saber quais outras famílias de hash são quase universais (como ), mas operam sobre (como ) e usam espaço e aleatoriedade.Z 2 b h 2 o ( m )h1Z2bh2o(m)

Existe uma família de hash? Seus membros podem ser avaliados em tempo?O(m)

jbapple
fonte

Respostas:

5

Sim. "Novas funções de hash e seu uso na autenticação e na igualdade de conjuntos" de Wegman e Carter ( espelho ) mostra um esquema que atende aos requisitos estabelecidos (quase universal, acima de , espaço sublinear e aleatoriedade, avaliação linear tempo) com base em um pequeno número de funções de hash extraídas de uma família fortemente universal.Z2b

Isso às vezes é chamado de "hash de árvore" e é usado em "Texugo - um MAC rápido e comprovadamente seguro" por Boesgaard et al .

jbapple
fonte
-1

Se você deseja algo rápido e que pode usar na prática, consulte a literatura criptográfica. Por exemplo, poly1305 e UMAC são rápidos e existem muitos outros. Como os hashes 2 universais são úteis para criptografia, os criptografadores estudaram muitas construções e descobriram que são extremamente eficientes.

O Poly1305 funciona como seu primeiro tipo de hash (chamado de hash de avaliação polinomial ), trabalhando no módulo . O esquema mostra truques inteligentes para tornar essa execução muito rápida em um computador moderno. A quantidade de aleatoriedade é pequena: 128 bits.21305

Se você deseja reduzir a quantidade de aleatoriedade e não se importa tanto com a praticidade, consulte o seguinte artigo de pesquisa:

  • Hashing e autenticação baseados em LFSR. Hugo Krawczyk. CRYPTO 1994.

Krawczyk descreve um sistema para reduzir a quantidade de aleatoriedade basicamente deixando ser do th da linha de uma matriz de Toeplitz. No entanto, o esquema de Krawczyk funciona sobre , não no módulo aritmético .aiiGF(2b)2b

DW
fonte
11
Agradeço suas referências, mas esta resposta não aborda a questão.
Jbapple #