Hash de cadena casi universal en

Aquí hay dos familias de funciones hash en las cadenas $\vec{x} = \langle x_0 x_1 x_2 \dots x_m \rangle$ :

1. $p$$x_i \in \mathbb{Z_p}$a ∈ Z p ∀ x ≠ y , P a ( h 1 a ( x ) = h 1 a ( y ) ) ≤ m /$h^1_{a}(\vec{x}) = \sum a^i x_i \bmod p$$a \in \mathbb{Z}_p$$\forall x \neq y, P_a(h^1_a(x) = h^1_a(y)) \leq m/p$

2. Para , para . Lemire y Kaser mostraron en "El hashing de cadenas fuertemente universal es rápido" que esta familia es independiente de 2. Esto implica que h 2 → un = ⟨ un 0 a 1 un 2 ... un m + 1 ⟩ ( → x ) = ( un 0 + Σ un i + 1 x i mod 2 2 b ) ÷ 2 b una i ∈ Z 2 2 b ∀ x ≠ y , $x_i \in \mathbb{Z}_{2^b}$$h^2_{\vec{a} = \langle a_0 a_1 a_2 \dots a_{m+1}\rangle}(\vec{x}) = (a_0 + \sum a_{i+1} x_i \bmod 2^{2b}) \div 2^b$$a_i \in \mathbb{Z}_{2^{2b}}$$\forall x \neq y, P_\vec{a}(h^2_\vec{a}(x) = h^2_\vec{a}(y)) = 2^{-b}$

$h^1$ usa solo bits de espacio y bits de aleatoriedad, mientras que usa bits de espacio y bits de aleatoriedad. Por otro lado, h ^ 2 opera sobre \ mathbb {Z} _ {2 ^ {2b}} , que es rápido en las computadoras reales.$\lg p$$h^2$$2 b m + 2 b$$h^2$$\mathbb{Z}_{2^{2b}}$

Me gustaría saber qué otras familias de hash son casi universales (como ), pero operan sobre (como ), y usan el espacio y aleatoriedad$h^1$$\mathbb{Z}_{2^b}$$h^2$$o(m)$

¿Existe tal familia hash? ¿Pueden sus miembros ser evaluados en tiempo?$O(m)$

Si. Las "Nuevas funciones hash de Wegman y Carter y su uso en la autenticación y la igualdad de conjunto" ( espejo ) muestran un esquema que cumple con los requisitos establecidos (casi universal, sobre , espacio sublineal y aleatoriedad, tiempo de evaluación lineal) basado en un pequeño número de funciones hash extraídas de una familia fuertemente universal.$\mathbb{Z}_{2^b}$

Esto a veces se llama "hashing de árbol", y Boesgaard et al . Lo utilizan en "Badger - Un MAC rápido y probablemente seguro" .

Si desea algo rápido y que puede usar en la práctica, puede consultar la literatura criptográfica. Por ejemplo, poly1305 y UMAC son rápidos, y hay muchos otros. Debido a que los hashes 2-universales son útiles para la criptografía, los criptógrafos han estudiado muchas construcciones y han encontrado algunas que son extremadamente eficientes.

Poly1305 funciona como su primer tipo de hash (llamado hash de evaluación polinomial ), funciona módulo . El esquema muestra trucos inteligentes para que esto funcione muy rápido en una computadora moderna. La cantidad de aleatoriedad es pequeña: 128 bits.$2^{130}-5$

Si desea reducir la cantidad de aleatoriedad y no le importa tanto la practicidad, puede consultar el siguiente trabajo de investigación:

• Hashing y autenticación basados ​​en LFSR. Hugo Krawczyk. CRYPTO 1994.

Krawczyk describe un esquema para reducir la cantidad de aleatoriedad básicamente al permitir que ser el i ésimo fila de una matriz de Toeplitz. Sin embargo, el esquema Krawczyk funciona sobre G F ( 2 b ) , no sobre el módulo aritmético 2 b .$a_i$$i$$GF(2^b)$$2^b$