Fast universelles String-Hashing im

9

Hier sind zwei Familien von Hash - Funktionen auf Strings :x=x0x1x2xm

  1. pxiZpha1(x)=aiximodpaZpxy,Pa(ha1(x)=ha1(y))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, dassxiZ2bha=a0a1a2am+12(x)=(a0+ai+1ximod22b)÷2baiZ22bxy,Pa(ha2(x)=ha2(y))=2b

h1 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.lgph22bm+2bh2Z22b

Ich würde gerne wissen, welche anderen Hash-Familien fast universell sind (wie ), aber über (wie ) operieren und Leerzeichen und verwenden Zufälligkeit.h1Z2bh2o(m)

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

jbapple
quelle

Antworten:

5

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.Z2b

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

jbapple
quelle
-1

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.21305

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 .aiiGF(2b)2b

DW
quelle
1
Ich schätze Ihre Referenzen, aber diese Antwort geht nicht auf die Frage ein.
jbapple