Schnittmenge von Listen mit vertraulichen Daten bestimmen

Dies geht an die Kryptologen unter Euch: Alice und Bob haben jeweils Listen mit vertraulichen Daten. Gesucht ist ein Verfahren, bei dem die Schnittmenge dieser Listen für beide bestimmbar wird, ohne dass der jeweils andere Kenntnis von den restlichen Elementen erlangt.

Alice und Bob könnten jedes einzelne Element ihrer leweiligen Liste kryptograhisch hashen. Dann die Liste der Hashes zur Bestimmung der Schnittmenge austauschen. Problem dabei: die Elemente sind Nummern, also sehr kleiner Zustandsraum. Damit könnten recht schnell Rainbow Tables berechnet werden. Im Moment gehen meine Überlegungen dahin, dass beide die Elemente ihrer Listen mit einem von beiden verwendeten Salt hashen. Dann ihre Listen an einen vertrauenswürdigen Dritten senden (deswegen das Salt, damit der Dritte keine Ranbow Tables berechnen kann). Der Dritte bestimmt dann die Schnittmenge und meldet Alice und Bob die Ergebnisse zurück.

Die Frage ist nun: Gibt es da nicht ein kryptographisches Verfahren ohne einen solchen Dritten?

*** Edit ***

Habe mit verschiedenen Suchbegriffen nun herausgefunden, wie das Problem heißt: “Private Set Intersection”. Lese mich da gerade etwas ein…

Wenn es vielleicht beim Suchen hilft: Dieses Problem gibt es in der Epidemiologie sehr oft, da Patientendaten anonymisiert zwischen Standorten abgeglichen werden müssen.

Hallo inv_zim, danke für den Tipp. Ich habe inzwischen Umfangreiche Abhandlungen zu den Verfahren gelesen. Alles sehr akademisch. Viel Gruppentheorie mit Formeln und so. Für mich nicht 100% verständlich. Bin halt “nur” Bindestrich-Informatiker. Auf meiner Suche nach Bibliotheken bin ich auf diverse Demoprojekte aus dem universitäeren Umfeld gestoßen. Nicht production ready. Wir werden bei dem naiven Hashing mit Salts und Austausch über einen vetrauenswürdigen Dritten bleiben.

Selbstgestrickte sicherheitsempfindliche Algorithmen sind immer problematisch, aber das weißt du ja sicher.
Für den Salt würde ich vorschlagen, dass Alice und Bob beide einen Bestandteil des Salt beisteuern, so liegt die Veranwortung nicht allein bei einem Teilnehmer. Alternativ könnte natürlich auch Ted (die vertrauenswürdige dritte Partei) den Salt vorgeben.

Nein Ted darf den salt nicht vorgeben, da sonst Ted eine rainbow attacke gegen die hashes fahren kann.

Damit hast du natürlich Recht, die Frage ist, inwieweit Ted vertrauenswürdig ist. Denn es scheint ja kein Problem zu sein, dass Ted die gesamte Menge der Informationen erhält.

Ted IST Vertrauen

Mit Bloomfiltern, könnte man recht einfach arbeiten um Datensätze auszusortieren, die das Gegenüber mit Sicherheit nicht hat.

Alice hasht ihre Datensätze und verknüpft alle Hashes mit logischem Oder. Das Ergebnis schickt sie an Bob.

Bob hasht seine Datensätze mit selber Hashfunktion und prüft jeden einzelnen Datensatz ob alle Bits in dem Ergebnis von Alice vorhanden sind. Sind sie es nicht kann man den Datensatz ausschließen.

Danach macht Bob das selbe wie Alice, allerdings nur auf den Datensätzen die noch nicht ausgeschlossen sind und evtl. mit einer anderen Hashfunktion.

Das ganze kann man dann mehrmals hin und her schicken bis nichts mehr wegfällt.

Nachteil: Bloomfilter haben false-positives. Ted wird anschließend immer noch gebraucht.

Vorteil: Je nach Datenmenge und Menge der Übereinstimmungen, kann man die Datenmenge recht schnell dezimieren. Ted hat weniger zu tun.
Daten die ausgeschlossen werden können bleiben geheim.

Der ist nicht selbstgestrickt. Das Verfahren wird sogar in den von mir gelesenen Papers genauso beschrieben. Natürlich mit den von mir hier auch genannten sicherheitstechnischen Einschränkungen. Es wird dort als “naives Hashing bezeichnet”. Die Attraktivität dieses Verfahrens besteht darin, dass es von allen bei weitem das schnellste und am besten skalierende ist (in meinem Fall nicht so wichtig die Mengen sind nicht groß). Und es ist super einfach zu implementieren. Es dient darum bei Benchmarks der fortgeschrittenen Verfahren immer als Referenz.

Denn es scheint ja kein Problem zu sein, dass Ted die gesamte Menge der Informationen erhält.

Doch ist es, deswegen bekommt Ted ja nicht die echten Daten, sondern gesalzene Hashwerte.

*** Edit ***

[QUOTE=ionutbaiu;144196]Mit Bloomfiltern, könnte man recht einfach arbeiten um Datensätze auszusortieren, die das Gegenüber mit Sicherheit nicht hat.

Alice hasht ihre Datensätze und verknüpft alle Hashes mit logischem Oder. Das Ergebnis schickt sie an Bob…[/QUOTE]
Danke für die Erklärung. Bloomfilter sind eines der in den Papers beschriebenen Verfahren. Habe aber auch die nicht verstanden. Nun etwas mehr.

das wäre nur ein technischer Nachteil,
an Sicherheit gibt es aber auch Abschläge:
von der Regenbogentabelle können potentiell sehr viele Werte, viel mehr als eigene (*), definitiv ausgeschlossen werden,
und alle anderen sind dann eben als mögliche Treffer bekannt, mit gewisser Wahrscheinlichkeit

zumindest im ersten Schritt für eine Seite, die den ersten Filter bekommt,

je genauer das Verfahren, desto kritischer,


(*) wie ist bei begrenzten Zustandsraum, genannt wurden Nummern, etwa 1-1000, eigentlich verhindert,
dass eine Seite eine Liste komplett von 1-1000 nimmt und damit die Schnittmenge prüft? :wink:

gut, Bloomfilter 11111111111 würde wohl nicht sehr viel bringen :wink:
eine Ted-Instanz müsste dazu aufpassen, auch dass nicht eine Seite mehrere Anfragen starten kann mit 1-10, 11-20 usw. …

Ich wollte dir nicht zu nahe treten. Es las sich für mich nach einem ersten eigenen Ansatz vor der Recherche. Dann ist das Thema in der Sicherheitsszene ja ausreichend diskutiert.

Bist Du nicht :wink: War tatsächlich zunächst mein Ansatz ohne Recherche. Ich hab jetzt eine Python Lib gefunden, die ich mir mal näher anschauen und versuchen werden, nach Java zu portieren: GitHub - mcoder/private-set-intersection: A python library providing several polynomial-based Private Set Intersection protocols.

Ich denke, das Problem, was SlaterB anspricht dürfte das größte Problem sein. Wenn ich beim Kartenspiel wissen will, welche Werte mein gegenüber auf der Hand hat, und selber alle vorhanden Karten nutzen kann, weiß ich sofort was er für Karten hat.