Gibt es einen kontinuierlichen Hash?

8

Fragen:

Kann es einen (kryptografisch sicheren) Hash geben, der die Informationstopologie von ?{0,1}

Können wir eine effizient berechenbare Nähe Prädikat , das weitergegeben wurden und (oder selbst) sagt uns , wenn ist sehr nahe an (zB die Levenshtein - Distanz oder Hamming - Distanz von und kleiner als ein fester Konstante )?hk(x)hk(y)yyxxyc


Hintergrund:

Mit Informationstopologie auf auf meine ich den Topologieraum mit Punkten und mit der Basis .ΣΣ{xΣ:xΣ}

Eine gute Möglichkeit, über die Topologie nachzudenken, besteht darin, offene Mengen als Eigenschaften von Punkten zu betrachten, die bejahbar / überprüfbar sind (dh wenn dies wahr ist, kann überprüft werden, ob es wahr ist). In diesem Sinne sind geschlossene Mengen widerlegbare Eigenschaften.

Eine Funktion ist stetig, wenn das inverse Bild von geöffneten Mengen offen ist. In unserem Fall bedeutet dies , dass für alle gibt es , so dass f:ΣΣyΣIΣ

f1(yΣ)=xIxΣ.

Eine gute Möglichkeit, über die Informationstopologie nachzudenken, besteht darin, sie als einen Baum von binären Zeichenfolgen zu betrachten. Jeder Teilbaum ist eine offene Basismenge (und eine andere offene Menge kann durch Zusammenführen von offenen Basismengen erhalten werden).

Dies wird manchmal als Informationstopologie von Zeichenfolgen bezeichnet, da jeder Punkt in als endliche Annäherung an eine binäre Zeichenfolge / Sequenz betrachtet werden kann. approximiert wenn eine anfängliche Teilzeichenfolge von ( ). ZB ist eine Annäherung an weil .Σxyxyxy0011Σ00110001100110

Und für die Kontinuität, wenn wir eine Folge die sich der binären Folge annähert und zu dieser konvergiert (denken Sie an{xi}iyy als einen unendlichen Zweig im Baum und s als Punkte auf diesem Zweig vor), dann { f ( x i ) } konvergiere zu f ( y ) , f ( y ) = i f ( x i ) .xi{f(xi)}f(y)

f(y)=if(xi).
Kaveh
quelle
Ich habe alles vergessen, was ich einmal über Topologie wusste. Wäre es möglich auszupacken, was es bedeutet, die Informationstopologie in eigenständigen Begriffen zu erhalten? Wenn Sie kryptografisch sicher sagen, welche Version davon meinen Sie damit? Meinen Sie "verhält sich wie ein zufälliges Orakel" oder "einseitig und kollisionssicher"?
DW
@DW Ich habe einige Erklärungen hinzugefügt, aber beim Schreiben stelle ich fest, dass meine erste Frage unklar ist. Ich muss ein bisschen nachdenken, um es zu klären. Die zweite Frage scheint in Ordnung zu sein.
Kaveh
1
Lokal sensibles Hashing kann relevant sein. en.wikipedia.org/wiki/Locality-sensitive_hashing
Zenna

Antworten:

5

Für moderne kryptografische Hash-Funktionen gibt es kein effizient berechenbares Prädikat für die Nähe, vorausgesetzt, die Verteilung auf weist eine ausreichende Entropie auf. Die Intuition ist, dass diese Hash-Funktionen so konzipiert sind, dass sie "keine Struktur haben", also lassen sie so etwas nicht zu.x

In technischer Hinsicht verhalten sich moderne kryptografische Hash-Funktionen "wie ein zufälliges Orakel". Für ein zufälliges Orakel gibt es kein solches Prädikat für die Nähe: Das Beste, was Sie tun können, scheint darin zu bestehen, die Hash-Funktion zu invertieren und dann alle engen Zeichenfolgen aufzulisten und zu hashen. Daher gibt es für moderne kryptografische Hash-Funktionen keine Möglichkeit, dies zu tun.

Heuristisch ist es möglich, eine benutzerdefinierte Hash-Funktion zu entwerfen, die ein effizientes Prädikat für die Nähe zulässt und die angesichts dieser Tatsache (ungefähr) "so sicher wie möglich" ist. Nehmen wir an, die Zeichenfolgen, die wir hashen werden, haben eine feste Länge. Angenommen, wir haben einen guten Fehlerkorrekturcode und lassen den Decodierungsalgorithmus sein (also ordnet er eine Bitfolge einem nahe gelegenen Codewort zu, wenn dies möglich ist).D.

Stellen Sie sich vor, Sie definieren um ein einfaches, aber unvollständiges Schema zu erhalten . Wenn x , y zwei zufällige Zeichenfolgen sind, die ausreichend nahe beieinander liegen, besteht eine gute Chance, dass h ( x ) = h ( y ) ist . Wenn x , y nicht nahe beieinander liegen, sieht h ( x ) nicht wie h ( y ) aus , und wir erhalten keine Informationen über die Tatsache hinaus, dass xh(x)=SHA256(D.(x))x,yh(x)=h(y)x,yh(x)h(y) sind nicht nah. Das ist einfach. Es ist jedoch auch unvollkommen. Es gibt viele Paare x , y , die nahe beieinander liegen, bei denen wir diese Tatsache jedoch nicht anhand von h ( x ) , h ( y ) erkennen können (z. B. weil die Decodierungsfunktion D fehlschlägt).x,yx,yh(x),h(y)D.

Heuristisch scheint es möglich zu sein, diese Konstruktion zu verbessern. Wählen Sie zur Entwurfszeit zufällige Bitfolgen . Definieren Sie nun die folgende Hash-Funktion:r1,,rk

h(x)=(SHA256(D.(xr1),,SHA256(D.(xrk)).

Wenn nun ausreichend nahe sind, ist es wahrscheinlich, dass i so existiert , dass D ( x r i ) = D ( y r i ) und somit h ( x ) i = h ( y ) i . Dies legt nahe , unmittelbar eine Nähe Prädikat: wenn h ( x ) übereinstimmt h ( y ) in einer ihrer k - Komponenten, dann x ,x,yichD.(xrich)=D.(yrich)h(x)ich=h(y)ichh(x)h(y)k sind nah; Andernfalls schließen Sie, dass sie nicht nahe sind.x,y

Wenn Sie zusätzlich Kollisionsfestigkeit wünschen, ist eine einfache Konstruktion die folgende: Sei eine Hash-Funktion mit einem Prädikat für die Nähe; dann ist h ( x ) = ( h 1 ( x ) , SHA256 ( x ) ) kollisionssicher (jede Kollision hierfür ist auch eine Kollision für SHA256) und hat ein Prädikat für die Nähe (verwenden Sie einfach das Prädikat für die Nähe für h 1 ). Sie können h 1 ( ) die oben definierte Hash-Funktion sein lassen.h1()h(x)=(h1(x),SHA256(x))h1h1()

Dies ist alles für die Hamming-Distanz. Der Bearbeitungsabstand ist wahrscheinlich erheblich schwieriger.

Bei der Entwicklung der obigen Konstruktion hat mich das folgende Papier inspiriert:

Ari Juels, Martin Wattenberg. Ein Fuzzy-Commitment-Schema .

Ari Juels, Madhi Sudhan. Ein Fuzzy-Vault-Schema . Designs, Codes und Kryptographie 38 (2): 237-257, 2006.

Übrigens: In der Kryptographie sind Hash-Funktionen nicht verschlüsselt. Wenn Sie eine Schlüsselsache möchten, sollten Sie sich Pseudozufallsfunktionen ansehen.

DW
quelle