Über-Schwellenwert-Mehrparteien-Private-Set-Intersection für kollaborative Netzwerk-Eindringlingserkennung

Grundinformationen

• Papier-ID: 2510.12045
• Titel: Over-Threshold Multiparty Private Set Intersection for Collaborative Network Intrusion Detection
• Autoren: Onur Eren Arpaci, Raouf Boutaba, Florian Kerschbaum (University of Waterloo)
• Klassifizierung: cs.CR (Kryptographie und Sicherheit), cs.NI (Netzwerk- und Internetarchitektur)
• Veröffentlichungsdatum: 14. Oktober 2025 (arXiv-Preprint)
• Papierlink: https://arxiv.org/abs/2510.12045

Zusammenfassung

Eine wichtige Funktion der kollaborativen Netzwerk-Eindringlingserkennung ist die Analyse von Netzwerkprotokollen der Zusammenarbeit, um gemeinsame IP-Adressen zu identifizieren. Das Teilen von IP-Adressen im Klartext ist jedoch sensibel und kann sogar unter Datenschutzgesetze fallen, da es sich um persönlich identifizierbare Informationen handelt. Dieses Papier schlägt eine datenschutzfreundliche Erfassungsmethode für IP-Adressen vor und präsentiert ein Protokoll für Über-Schwellenwert-Private-Set-Intersection mit einem einzelnen Aggregator. In diesem Protokoll identifizieren N Teilnehmer IP-Adressen, die in den Mengen von mindestens t Teilnehmern erscheinen, ohne Informationen über andere IP-Adressen preiszugeben. Durch ein neuartiges Hash-Schema wird die Rechenkomplexität der bisherigen hochmodernen Lösung von $O(M(N \log{M}/t)^{2t})$ auf $O(t^2M\binom{N}{t})$ reduziert, wobei M die Datensatzgröße darstellt. Diese Reduktion macht die Anwendung des Protokolls auf echte Netzwerkprotokolle praktisch machbar.

Forschungshintergrund und Motivation

Problemdefinition

Das Kernproblem der kollaborativen Netzwerk-Eindringlingserkennung besteht darin, wie Angriffe mehrerer Institutionen unter Wahrung der Privatsphäre identifiziert werden können. Untersuchungen zeigen, dass 75% der Angriffe auf mehrere Institutionen sich innerhalb eines Tages auf eine zweite Institution ausbreiten, und über 40% breiten sich innerhalb einer Stunde aus. Angreifer nutzen typischerweise eine kleine Anzahl externer IP-Adressen, um mehrere Institutionen gleichzeitig anzugreifen. Wenn eine externe IP innerhalb eines bestimmten Zeitfensters mit mindestens t Institutionen verbunden ist, kann sie mit 95% Rückrufquote als bösartig klassifiziert werden.

Datenschutzherausforderungen

Traditionelle Methoden erfordern, dass Institutionen Netzwerkprotokolle im Klartext teilen, was erhebliche Datenschutzrisiken mit sich bringt:

1. Rechtliche Compliance: IP-Adressen werden von GDPR, PIPEDA, CCPA und anderen Gesetzen als persönlich identifizierbare Informationen definiert
2. Datensensibilität: Rohdaten des Netzwerks sind empfindlicher als Sicherheitswarnungen und enthalten große Mengen irrelevanter sensibler Informationen
3. Datengröße: Rohdaten sind mehrere Größenordnungen größer als Sicherheitswarnungen, was bestehende Lösungen rechnerisch nicht machbar macht

Einschränkungen bestehender Methoden

• Kissner and Song 26: Benötigt O(N) Kommunationsrunden, Rechenkomplexität O(N³M³)
• Mahdavi et al. 34: Obwohl die Kommunationskomplexität verbessert wurde, bleiben die Rechenkosten zu hoch mit einer Komplexität von O(M(N logM/t)²ᵗ)

Kernbeiträge

1. Neuartiges Hash-Schema: Präsentiert einen innovativen Hash-Algorithmus, der die Rechenkomplexität von O(M(N logM/t)²ᵗ) auf O(t²M(N choose t)) reduziert und lineare Komplexität in M erreicht
2. Praktische Verbesserung: Ermöglicht dem Protokoll, Netzwerkprotokolle in realer Größe zu verarbeiten, wobei die Erkennung in 170 Sekunden mit 33 teilnehmenden Institutionen und bis zu 144.045 IPs abgeschlossen wird
3. Duale Bereitstellungsoptionen:
   • Kollusions-resistente Bereitstellung: Bietet stärkere Sicherheitsgarantien, aber höhere Kommunikationskosten
   • Nicht-interaktive Bereitstellung: Setzt einen nicht-kollusiven Aggregator voraus, reduziert Kommunikationskosten erheblich
4. Sicherheitsbeweis: Beweist die Sicherheit des Protokolls im halbehrlichen Mehrparteien-Berechnungsmodell
5. Praktische Validierung: Evaluierung mit echten Netzwerkprotokollen aus dem CANARIE-IDS-Projekt

Methodische Details

Aufgabendefinition

Über-Schwellenwert-Mehrparteien-Private-Set-Intersection (OT-MP-PSI):

• Eingabe: N Teilnehmer, jeder hält eine Menge Si mit höchstens M Elementen
• Ausgabe: Identifiziert Elemente, die in mindestens t Mengen erscheinen, ohne Informationen über Elemente unterhalb des Schwellenwerts preiszugeben
• Einschränkung: Halbehrliches Sicherheitsmodell, Teilnehmer befolgen das Protokoll, können aber versuchen, zusätzliche Informationen zu erfahren

Kernkomponenten der Technik

1. Shamir-Geheimnisfreigabe

Verwendet ein (t,n)-Schwellenwertschema, bei dem jede t-Partei das Geheimnis V rekonstruieren kann, während weniger als t Parteien keine Informationen erhalten:

P(x) = c_{t-1}x^{t-1} + c_{t-2}x^{t-2} + ... + c_1x + V

2. Oblivious Pseudorandom Function (OPRF)

Teilnehmer erfahren H_K(x), ohne den Schlüssel K zu kennen; der Schlüsselhalter kennt weder die Eingabe x noch die Ausgabewerte.

3. Oblivious Pseudorandom Secret Sharing (OPR-SS)

Kombiniert die Sicherheitseigenschaften von Geheimnisfreigabe und OPRF und ermöglicht Teilnehmern, eindeutige Geheimnisanteile vom Schlüsselhalter zu erhalten.

Protokollarchitektur

Nicht-interaktive Bereitstellung

1. Anteilserstellung: Jeder Teilnehmer erstellt Geheimnisanteile für jedes Element in seiner Menge
2. Hash-Zuordnung: Verwendet das neue Hash-Schema, um Anteile auf Behälter der Größe 1 abzubilden
3. Rekonstruktion: Der Aggregator versucht Lagrange-Interpolation für alle Kombinationen von t Teilnehmern
4. Ergebnisbenachrichtigung: Der Aggregator benachrichtigt Teilnehmer über erfolgreich rekonstruierte Indizes

Kollusions-resistente Bereitstellung

Verwendet das OPR-SS-Protokoll anstelle gemeinsamer Schlüssel, berechnet die Hash-Funktion durch Multi-Schlüssel-OPRF-Protokoll und bietet stärkere Kollusions-Resistenz.

Technische Innovationspunkte

Neues Hash-Schema

Kernidee: Verwendet Behälter der Größe 1, um Hash-Kollisionen zu vermeiden, anstatt sie zu beherbergen:

1. Kollisionsbehandlung: Wenn mehrere Elemente auf denselben Behälter abgebildet werden, wird das kleinste Element durch pseudozufällige Sortierung ausgewählt
2. Multi-Tabellen-Strategie: Jeder Teilnehmer erstellt mehrere Tabellen, um sicherzustellen, dass fehlende Werte in anderen Tabellen erscheinen
3. Fehlerwahrscheinlichkeitskontrolle: Kontrolliert die Fehlerwahrscheinlichkeit auf unter 2⁻⁴⁰ durch 20 Tabellen

Wichtigste Vorteile:

• Der Aggregator muss nur Teilnehmerkombinationen versuchen, nicht Anteilskombinationen
• Komplexität sinkt von exponentiell auf linear (bezüglich M)
• Vermeidet große konstante Faktoren traditioneller Bucketing-Methoden

Optimierungstechniken

1. Sortierungsumkehrung: Aufeinanderfolgende zwei Tabellen verwenden dieselbe Sortierfunktion, gerade Tabellen kehren die Sortierung um
2. Leere-Behälter-Nutzung: Zweites Einfügen nutzt leere Behälter nach dem ersten Einfügen

Experimentelle Einrichtung

Datensätze

• Echte Daten: Netzwerkverbindungsprotokolle von 54 Institutionen aus dem CANARIE-IDS-Projekt
• Zeitbereich: 1.-8. November 2023, etwa 8 Milliarden Protokolleinträge pro Tag
• Datengröße: Etwa 700 GB pro Tag (gzip-komprimiert)
• Verarbeitungsweise: Verarbeitung in stündlichen Chargen, Extraktion externer IP zu interner IP-Verbindungen

Bewertungsmetriken

• Rekonstruktionszeit: Zeit für den Aggregator, die Rekonstruktion abzuschließen
• Anteilserstellungszeit: Zeit für einen einzelnen Teilnehmer, Anteile zu erstellen
• Kommunationskomplexität: Gesamtkommunikationsaufwand des Protokolls
• Korrektheit: Validierung der Fehlerwahrscheinlichkeit

Vergleichsmethoden

• Mahdavi et al. 34: Aktuelle hochmoderne OT-MP-PSI-Lösung
• Theoretische Obergrenzen: Vergleich mit berechneten Fehlerwahrscheinlichkeitsgrenzen

Implementierungsdetails

• Programmiersprache: Julia, 430 Codezeilen
• Kryptographische Bibliotheken: SHA.jl, Nettle.jl
• Endliches Feld: 61-Bit-Mersenne-Primzahl
• Hardwareumgebung: 8×Intel Xeon E7-8870-Prozessoren, 80 physische Kerne, 1 TB Speicher

Experimentelle Ergebnisse

Hauptergebnisse

Leistungsvergleich

Im Vergleich zu Mahdavi et al. 34:

• Geschwindigkeitssteigerung: Mindestens zwei Größenordnungen, bis zu 23.066-fach
• Skalierbarkeit: Bei M=10⁵ benötigt diese Methode Hunderte von Sekunden, die Vergleichsmethode benötigt Tage

Leistung bei echten Daten

Leistung auf CANARIE-Daten:

• Durchschnittliche Rekonstruktionszeit: 170 Sekunden
• Maximale Rekonstruktionszeit: 438 Sekunden (40 Institutionen, 220.011 IPs)
• Durchschnittliche teilnehmende Institutionen: 33
• Durchschnittliche maximale Mengengröße: 144.045 IPs

Komplexitätsanalyse

Rechenkomplexität

• Aggregator: O(t²M(N choose t))
• Teilnehmer (nicht-interaktiv): O(tM)
• Spezialfall: N=t=2 ist O(M), N=t ist O(N²M)

Kommunationskomplexität

• Nicht-interaktive Bereitstellung: O(tMN)
• Kollusions-resistente Bereitstellung: O(tkMN), 5 Kommunationsrunden

Korrektheit-Validierung

• Theoretische Fehlerwahrscheinlichkeit: 2⁻⁴⁰
• Experimentelle Validierung: In 10⁷ Versuchen liegt die tatsächliche Fehlerquote weit unter der theoretischen Obergrenze
• Tabellenoptimierung: Von theoretischen 28 Tabellen auf praktische 20 Tabellen optimiert

Verwandte Arbeiten

OT-MP-PSI-Lösungen

1. Kissner and Song 26: Erste Lösung, verwendet Polynomring-Darstellung, O(N³M³)-Komplexität
2. Mahdavi et al. 34: Konstante Runden, O(M(N logM/t)²ᵗ)-Komplexität
3. Ma et al. 33: Geeignet für kleine Eingabemengen und kleine Domänen, O(N|S|)-Komplexität

Verwandte Probleme

• Threshold Private Set Intersection (TPSI): Lernt Schnittmenge nur wenn Schnittmenge-Größe Schwellenwert überschreitet
• Quorum-PSI: Spezialfall von OT-MP-PSI, nur bestimmte Teilnehmer haben Ausgabe

Hash-Techniken

• Cuckoo Hashing: Zur Vermeidung von Hash-Kollisionen, weit verbreitet in PSI-Protokollen
• 2D Cuckoo Hashing: Speziell für zwei-Parteien-PSI entwickelt, erreicht O(M)-Komplexität

Schlussfolgerungen und Diskussion

Hauptschlussfolgerungen

1. Praktischer Durchbruch: Macht OT-MP-PSI erstmals bei echten Netzwerkprotokoll-Größen praktisch machbar
2. Effizienzsteigerung: Erreicht Leistungsverbesserungen in Größenordnungen durch neues Hash-Schema
3. Flexible Bereitstellung: Bietet zwei Bereitstellungsoptionen für unterschiedliche Sicherheitsanforderungen
4. Praktische Validierung: Validiert die Praktikabilität des Protokolls in echter Multi-Institutionen-Netzwerkumgebung

Einschränkungen

1. Halbehrliches Modell: Obwohl auf böswilliges Modell erweiterbar, anfällig für Eingabeersatz-Angriffe
2. Mengengröße-Offenlegung: Kernprotokoll behandelt Teilnehmer-Mengengröße nicht als private Information
3. Aggregator-Vertrauen: Nicht-interaktive Bereitstellung erfordert Vertrauen, dass der Aggregator nicht mit Teilnehmern kolludiert
4. Schwellenwert-Einschränkung: Wenn t nahe N/2 liegt und N sehr groß ist, kann der Komplexitätsvorteil nicht signifikant sein

Zukünftige Richtungen

1. Böswillige Sicherheit: Erweiterung des Protokolls zur Abwehr aktiver Angreifer
2. Dynamische Schwellenwerte: Unterstützung von Multi-Schwellenwert-Berechnungen ohne zusätzliche Client-Kosten
3. Großskaliger-Optimierung: Weitere Optimierung der Verarbeitung von Teilnehmerkombinationen
4. Datenschutz-Verbesserung: Erkundung differentieller Datenschutztechniken zum Schutz von Mengengröße-Informationen

Tiefgreifende Bewertung

Stärken

1. Signifikanter theoretischer Beitrag: Neues Hash-Schema ist ein wichtiger Durchbruch in bestehender Technik, reduziert exponentielle Komplexität auf lineare
2. Hoher praktischer Wert: Löst kritisches Datenschutzproblem in echter kollaborativer Eindringlingserkennung
3. Umfassende Experimente: Bietet sowohl theoretische Analyse als auch echte Datenvalidierung mit angemessenem experimentellem Design
4. Vollständige Ingenieurimplementierung: Bietet Open-Source-Implementierung, verbessert Reproduzierbarkeit
5. Strikte Sicherheit: Bietet formale Sicherheitsbeweise und zwei Bereitstellungsoptionen

Mängel

1. Sicherheitsmodell-Einschränkung: Halbehrliches Modell kann in einigen praktischen Szenarien nicht ausreichend stark sein
2. Parameterwahl: Wahl von 20 Tabellen basiert auf empirischer Optimierung, theoretische Anleitung ist unzureichend
3. Skalierungsgrenzen: Anwendbarkeit auf extrem große Maßstäbe (z.B. globales Internet-Niveau) wurde nicht ausreichend untersucht
4. Begrenzte Vergleichsbasis: Hauptsächlich Vergleich mit einer Baseline-Methode, mangelnde umfassendere Leistungsvergleiche

Auswirkungen

1. Akademischer Wert: Bietet neuen technischen Weg für Mehrparteien-Sicherheitsberechnungsfeld
2. Praktische Bedeutung: Löst direkt echte Anforderungen im Netzwerksicherheitsbereich
3. Technische Verbreitung: Hash-Schema kann auf andere Mehrparteien-Berechnungsprobleme anwendbar sein
4. Standardisierungspotenzial: Könnte zum Standard-Protokoll für kollaborative Eindringlingserkennung werden

Anwendungsszenarien

1. Multi-Institutionen-Netzwerksicherheit: Kollaborativer Schutz ähnlicher Institutionen wie Universitäten, Krankenhäuser
2. Cloud-Sicherheitsdienste: Datenschutz-geschützte Protokoll-Analyse in Security Operations Centers
3. Threat-Intelligence-Austausch: Austausch von Threat-Indikatoren unter Datenschutzbeschränkungen
4. Compliance-Anforderungen: Datenzusammenarbeit unter Einhaltung von GDPR und anderen Datenschutzbestimmungen

Literaturverzeichnis

Dieses Papier zitiert 53 verwandte Literaturquellen, die wichtige Arbeiten in mehreren Bereichen wie Kryptographie, Netzwerksicherheit und Mehrparteien-Berechnung abdecken und eine solide theoretische Grundlage und umfassenden technischen Hintergrund für die Forschung bieten.

Gesamtbewertung: Dies ist ein hochqualitatives Papier der angewandten Kryptographie, das ein gutes Gleichgewicht zwischen theoretischer Innovation und praktischer Anwendung erreicht. Das neu vorgeschlagene Hash-Schema stellt nicht nur einen wichtigen theoretischen Durchbruch dar, sondern zeigt auch signifikanten Wert in praktischen Anwendungen. Die experimentelle Validierung des Papiers ist umfassend, die Sicherheitsanalyse ist streng und bietet wichtige technische Beiträge für das Feld der kollaborativen Netzwerksicherheit.