Fast universelles String-Hashing im

Hier sind zwei Familien von Hash - Funktionen auf Strings :$\vec{x} = \langle x_0 x_1 x_2 \dots x_m \rangle$

1. $p$$x_i \in \mathbb{Z_p}$$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. Für gilt für . Lemire und Kaser zeigten in "Stark universelles String-Hashing ist schnell", dass diese Familie 2-unabhängig ist. Dies impliziert, dass$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$ verwendet nur Bits des Raumes und der Bits der Zufälligkeit, während Verwendungen Bits des Raumes und der Bits der Zufälligkeit. Andererseits arbeitet über , was auf tatsächlichen Computern schnell ist.$\lg p$$h^2$$2 b m + 2 b$$h^2$$\mathbb{Z}_{2^{2b}}$

Ich würde gerne wissen, welche anderen Hash-Familien fast universell sind (wie ), aber über (wie ) operieren und Leerzeichen und verwenden Zufälligkeit.$h^1$$\mathbb{Z}_{2^b}$$h^2$$o(m)$

Gibt es eine solche Hash-Familie? Können seine Mitglieder in Zeit bewertet werden?$O(m)$

Ja. Wegmans und Carters "Neue Hash-Funktionen und ihre Verwendung bei der Authentifizierung und Mengengleichheit" ( Spiegel ) zeigt ein Schema, das die angegebenen Anforderungen erfüllt (nahezu universell, über , sublinearer Raum und Zufälligkeit, lineare Auswertung Zeit) basierend auf einer kleinen Anzahl von Hash-Funktionen, die aus einer stark universellen Familie stammen.$\mathbb{Z}_{2^b}$

Dies wird manchmal als "Tree Hashing" bezeichnet und wird in "Badger - A Fast and Provably Secure MAC" von Boesgaard et al .

Wenn Sie etwas schnelles wollen und das Sie in der Praxis verwenden können, können Sie sich die kryptografische Literatur ansehen. Zum Beispiel sind poly1305 und UMAC schnell und es gibt viele andere. Da 2-universelle Hashes für die Kryptographie nützlich sind, haben Kryptographen viele Konstruktionen untersucht und solche gefunden, die äußerst effizient sind.

Poly1305 funktioniert wie Ihr erster Hash-Typ (als Polynom-Evaluierungs-Hash bezeichnet ) und funktioniert modulo . Das Schema zeigt clevere Tricks, um dies auf einem modernen Computer sehr schnell laufen zu lassen. Die Zufälligkeit ist gering: 128 Bit.$2^{130}-5$

Wenn Sie die Zufälligkeit reduzieren möchten und sich nicht so sehr für die Praktikabilität interessieren, lesen Sie möglicherweise das folgende Forschungspapier:

• LFSR-basiertes Hashing und Authentifizierung. Hugo Krawczyk. CRYPTO 1994.

Krawczyk beschreibt ein Schema zur Reduzierung der Zufälligkeit, indem die te Zeile einer Toeplitz-Matrix ist. Das Krawczyk-Schema funktioniert jedoch über , nicht über das arithmetische Modulo .$a_i$$i$$GF(2^b)$$2^b$