🤖 AI

P $^2$ RAG: Efficient Privacy-Preserving RAG Service Supporting Arbitrary Top- $k$ Retrieval

Das Papier schlägt P $^2$ RAG vor, einen effizienten, datenschutzkonformen Retrieval-Augmented-Generation-Dienst, der eine interaktive Bisektionsmethode und Secret Sharing nutzt, um eine beliebige Top- $k$ -Retrieval ohne sichere Sortierung zu unterstützen, wodurch im Vergleich zu bestehenden Systemen erhebliche Geschwindigkeitssteigerungen erzielt werden, während sowohl Daten als auch Benutzer-Prompts geschützt bleiben.

Ursprüngliche Autoren: Yulong Ming, Mingyue Wang, Jijia Yang, Jie Xu, Zihan Wu, Cong Wang, Xiaohua Jia

Veröffentlicht 2026-05-29

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Yulong Ming, Mingyue Wang, Jijia Yang, Jie Xu, Zihan Wu, Cong Wang, Xiaohua Jia

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie besitzen eine massive, geheime Bibliothek von Dokumenten (wie medizinische Aufzeichnungen, rechtliche Verträge oder Finanzberichte), die Sie zur Beantwortung von Fragen nutzen möchten. Sie möchten die gesamte Bibliothek nicht an ein Suchmaschinenunternehmen übergeben, da sie zu sensibel ist. Gleichzeitig möchten Sie nicht, dass die Suchmaschine genau weiß, wonach Sie fragen, da dies Ihre privaten Gedanken oder Geschäftsstrategien offenlegt.

Dies ist das Problem, das P2RAG löst. Es ist eine neue Methode, um einen „Retrieval-Augmented Generation" (RAG)-Dienst auszuführen – ein ausgefallener Begriff für „eine KI, die Fragen mithilfe Ihrer privaten Dokumente beantwortet" –, ohne dass jemand die Geheimnisse einsehen kann.

So funktioniert es, aufgeteilt in einfache Konzepte:

1. Der alte Weg: Sortieren des gesamten Decks

Stellen Sie sich ein Deck von 1.000 Karten vor, jede mit einem Punktwert. Sie möchten die 10 Karten mit den höchsten Punktwerten finden.

Das Problem: In früheren sicheren Systemen musste der Computer, um die Top 10 zu finden, jede einzelne Karte geheim mit jeder anderen Karte vergleichen, um sie von höchstem zu niedrigstem Wert zu sortieren. Es ist, als würde man versuchen, die größte Person in einer Menge zu finden, indem man alle aufstellt und sie einzeln misst, dies jedoch so durchführt, dass niemand die Messungen sehen kann.
Der Flaschenhals: Wenn Sie statt 10 die Top 100 Karten wollen, wird dieser „Sortier"-Prozess unglaublich langsam und teuer. Es ist, als würde man versuchen, eine Bibliothek von Büchern nur zu sortieren, um die 5 besten zu finden; je mehr Bücher Sie haben, desto länger dauert es.

2. Die P2RAG-Lösung: Das „Raten der Schwelle"-Spiel

P2RAG verändert das Spiel. Anstatt das gesamte Deck zu sortieren, spielt es ein Spiel von „Heiß und Kalt" (speziell eine binäre Suche oder „Bisektion"), um eine Grenzwertlinie zu finden.

Der Aufbau: Stellen Sie sich zwei Server vor (nennen wir sie Server A und Server B), die die geheime Bibliothek halten. Sie teilen jedes Dokument in zwei Hälften, sodass kein Server die ganze Geschichte kennt. Sie (der Benutzer) teilen auch Ihre Frage in zwei Hälften und senden ein Stück an jeden Server.
Das Spiel:
1. Sie fragen die Server: „Wie viele Dokumente sind ähnlich genug zu meiner Frage, wenn wir die Schwelle auf diesem spezifischen Niveau setzen?"
2. Die Server zählen die Treffer, ohne Ihnen zu sagen, welche Dokumente es sind, und ohne dass Sie die Punktwerte sehen. Sie sagen nur: „Es gibt 50 Treffer."
3. Sie denken: „Ich wollte nur 10. Das sind zu viele. Lassen Sie uns die Schwelle erhöhen."
4. Sie fragen erneut mit einer höheren Schwelle. Sie sagen: „Jetzt gibt es 5 Treffer."
5. Sie denken: „Zu wenige. Lassen Sie uns die Schwelle etwas senken."
6. Sie passen die Schwelle hin und her an, bis die Anzahl genau dem entspricht, was Sie benötigen (z. B. 10 Dokumente).

Die Magie: Da Sie nur eine „Schwelle" anpassen und zählen, müssen Sie nicht die gesamte Bibliothek sortieren. Sie müssen nur die richtige Höhe für die Schwelle finden. Dies macht den Prozess unglaublich schnell, selbst wenn Sie eine große Anzahl von Ergebnissen wünschen (wie 1.000 Dokumente).

3. Geheimnisse sicher halten (Die „Kein-Vertrauen"-Regel)

Die Arbeit behauptet, dass dieses System sicher ist, selbst wenn die Server „ehrlich aber neugierig" sind (sie folgen den Regeln, versuchen aber zu schnüffeln) oder wenn der Benutzer „böswillig" ist (versucht, das System zu täuschen).

Gegen neugierige Server: Da die Daten aufgeteilt (geheimgeteilt) sind, sieht Server A nur ein zufälliges Durcheinander von Zahlen, und Server B sieht ein anderes zufälliges Durcheinander. Keiner kann das Dokument oder Ihre Frage rekonstruieren, es sei denn, sie arbeiten zusammen. Die Arbeit geht davon aus, dass sie nicht zusammenarbeiten (wie zwei verschiedene Unternehmen in verschiedenen Ländern).
Gegen hinterhältige Benutzer: Ein trickreicher Benutzer könnte versuchen, die Server zu bitten, die Schwelle so niedrig zu setzen, dass alle Dokumente übereinstimmen, wodurch effektiv die gesamte Bibliothek gestohlen wird. P2RAG setzt ein „Tempolimit" für die Anzahl der Anfragen und überprüft die Mathematik, um sicherzustellen, dass Sie nur die Dokumente erhalten, die Sie sehen dürfen. Es begrenzt streng, wie viel Information ein böser Benutzer stehlen kann.

4. Warum dies wichtig ist (Die Ergebnisse)

Die Autoren testeten dieses System und stellten fest:

Geschwindigkeit: Es ist 3- bis 300-mal schneller als die derzeit besten sicheren Systeme, wenn Sie eine große Anzahl von Dokumenten abrufen möchten (von 16 bis zu 1.024).
Flexibilität: Sie können nach jeder Anzahl von Ergebnissen fragen (beliebiges k), was für Bereiche wie Finanzen oder Recht entscheidend ist, wo Sie möglicherweise viel Kontext sehen müssen, um die richtige Antwort zu erhalten.
Genauigkeit: Das System ist so präzise, dass es exakt dieselben Dokumente findet wie ein nicht-sicheres System, mit fast keinen mathematischen Fehlern.

Das Fazit

P2RAG ist wie ein sicherer, hochgeschwindigkeitsfähiger Bibliothekar, der Ihre spezifischen Dokumente in einem massiven, verschlossenen Tresor finden kann, ohne jemals den Tresor zu öffnen, um Ihnen die Bücher zu zeigen, und ohne dass Sie jemals die anderen Bücher im Tresor sehen. Dies erreicht er, indem er ein intelligentes Ratespiel spielt, um den „Grenzwert" zu finden, anstatt die gesamte Sammlung zu sortieren, was es schnell genug macht, um in der realen Welt nützlich zu sein.

Technische Zusammenfassung von P2RAG: Ein effizienter, datenschutzfreundlicher RAG-Dienst zur Unterstützung beliebiger Top-k-Abfragen

Problemstellung
Retrieval-Augmented Generation (RAG) ermöglicht es Large Language Models (LLMs), externes Wissen zu nutzen, doch die Auslagerung von RAG-Diensten birgt erhebliche Datenschutzrisiken sowohl für Dateninhaber (deren proprietäre Datenbanken offengelegt werden) als auch für Nutzer (deren Prompts sichtbar sind). Bestehende datenschutzfreundliche RAG-Systeme (PP-RAG) betrachten das Problem typischerweise als sichere Top-k-Abfrage und setzen dabei auf sichere Sortierung oder sichere k-Approximate Nearest Neighbor (k-ANN)-Techniken. Diese Systeme weisen jedoch kritische Einschränkungen auf:

Inflexibilität: Sie können oft keine beliebigen oder dynamischen Anpassungen des Abfrageparameters $k$ unterstützen.
Leistungsverschlechterung: Ihre Leistung verschlechtert sich erheblich, wenn $k$ steigt. Dies stellt einen wesentlichen Engpass dar, da moderne Anwendungen in Finanzen, Recht und Gesundheitswesen sowie Long-Context-LLMs häufig große $k$ -Werte (z. B. 100–150 oder höher) benötigen, um eine optimale Genauigkeit zu erreichen.
Sicherheitslücken: Einige bestehende Ansätze werfen neue Sicherheitsprobleme auf oder versagen darin, die Informationspreisgabe gegenüber böswilligen Nutzern eng zu begrenzen.

Methodik
Die Autoren stellen P2RAG vor, einen datenschutzfreundlichen RAG-Dienst, der entwickelt wurde, um beliebige Top-k-Abfragen effizient zu unterstützen. Das System arbeitet auf einem Zwei-Server-Modell, bei dem die Server semi-ehrlich (ehrlich, aber neugierig) sind und nicht kolludieren.

Systemarchitektur:
- Dateninhaber: Lagert eine verschlüsselte Datenbank auf zwei Servern aus. Die Datenbank besteht aus $N$ Dokument-Embeddings, die mittels Shamir-Geheimnisverteilung über einem Primfeld zwischen den beiden Servern geheimgeteilt werden.
- Nutzer: Sendet ein Prompt-Embedding, das ebenfalls zwischen den beiden Servern geheimgeteilt wird.
- Bedrohungsmodell: Die Server folgen dem Protokoll, versuchen jedoch möglicherweise, Daten zu erschließen. Nutzer werden als böswillig modelliert und können vom Protokoll abweichen, um Informationen zu extrahieren. Dateninhaber werden als ehrlich angenommen.
Kerninnovation: Interaktive Bisektion versus Sortierung
Im Gegensatz zu bestehenden Systemen, die alle Kandidatendokumente sortieren (eine in sicheren Protokollen rechenintensive Operation), vermeidet P2RAG die Sortierung vollständig. Stattdessen wendet es eine interaktive Bisektionsmethode an, um einen Distanzschwellenwert ( $d_k$ ) zu bestimmen, der die Top- $k$ -Menge definiert.
1. Distanzberechnung: Die Server berechnen geheimgeteilte Kosinusdistanzen (approximiert über Skalarprodukte) zwischen dem Prompt des Nutzers und allen Dokument-Embeddings unter Verwendung von Beaver-Tripeln.
2. Bisektionsiteration: Der Nutzer und die Server interagieren, um einen Distanzschwellenwert einzugrenzen. In jeder Iteration gibt der Nutzer einen Schwellenwert $d_k$ vor. Die Server verwenden Distributed Comparison Functions (DCFs), um zu zählen, wie viele Dokumente Distanzen kleiner als $d_k$ aufweisen.
3. Schwellenwertauswahl: Der Nutzer aktualisiert $d_k$ basierend auf der zurückgegebenen Anzahl, bis die Anzahl der Dokumente innerhalb des Schwellenwerts nahe am Zielwert $k$ liegt.
4. Ergebnisabruf: Sobald der Schwellenwert bestimmt ist, generieren die Server einen geheimgeteilten Binärvektor, der angibt, welche Dokumente innerhalb des Schwellenwerts liegen. Der Nutzer ruft die Indizes dieser Dokumente mittels Single-Server Private Information Retrieval (PIR) ab.
Sicherheitsmechanismen:
- Datenschutz: Geheimteilung stellt sicher, dass kein Server die Datenbank oder den Prompt erfährt.
- Verteidigung gegen böswillige Nutzer: Um zu verhindern, dass Nutzer übermäßige Informationen extrahieren, erzwingt P2RAG strenge Beschränkungen:
  - Die Anzahl der Bisektionsiterationen ist begrenzt (was die gesamte Mengenpreisgabe auf $O(\log^2 N)$ beschränkt).
  - Die Größe des Endergebnissatzes ist begrenzt.
  - Verifikationsmechanismen stellen sicher, dass der Nutzer nur Indizes abruft, die dem vereinbarten Binärvektor entsprechen, und verhindert so Manipulationen des Abfrageprozesses.

Hauptbeiträge

Unterstützung beliebiger Top-k-Abfragen: P2RAG ist das erste System, das beliebige $k$ -Werte effizient unterstützt, ohne die bei sortierungsbasierten Ansätzen auftretende Leistungsverschlechterung, und eignet sich somit für große $k$ -Szenarien, die von modernen Long-Context-Modellen benötigt werden.
Effizientes Protokoll-Design: Durch den Ersatz der sicheren Sortierung durch eine interaktive Bisektionsmethode unter Verwendung von DCFs reduziert P2RAG die Anzahl der Vergleiche erheblich, die den Hauptengpass in sicheren Protokollen darstellen.
Robuste Sicherheit: Das System schützt sowohl die Datenbank des Dateninhabers als auch den Prompt des Nutzers vor semi-ehrlichen Servern. Es führt zudem spezifische Beschränkungen und Verifikationsschritte ein, um die Informationspreisgabe gegenüber böswilligen Nutzern eng zu begrenzen.
Implementierung und Evaluation: Die Autoren haben P2RAG implementiert und den Code unter der Apache-Lizenz 2.0 veröffentlicht.

Experimentelle Ergebnisse
Die Autoren evaluierten P2RAG unter Verwendung von BEIR-Datensätzen (z. B. trec-covid mit ca. 171.000 Dokumenten) und synthetischen Datensätzen.

Genauigkeit: P2RAG erzielt eine hohe rechnerische Genauigkeit. Der Recall bleibt bei $k'$ -Werten von 16 bis 1024 bei 1,0, und Relevanzwerte deuten darauf hin, dass die abgerufenen Dokumente im Allgemeinen für den Prompt relevant sind.
Leistung: P2RAG zeigt im Vergleich zum State-of-the-Art-System PRAG erhebliche Geschwindigkeitssteigerungen.
- Für $k = 16$ ist P2RAG 3,78-mal schneller.
- Für größere $k$ (z. B. $k=1024$ ) steigt der Geschwindigkeitsvorteil auf 322-mal.
- Das System skaliert linear mit der Anzahl der Dokumente ( $N$ ), wird jedoch relativ schneller, wenn $k$ steigt, im Gegensatz zu PRAG, das unter einer Leistungsverschlechterung leidet.
Kommunikation: Während die Kommunikation zwischen den Servern Hunderte von Megabyte erreichen kann, ist dies über hochbandbreite Datenzentrum-Verbindungen handhabbar. Die Kommunikation zwischen Nutzer und Server bleibt gering (vergleichbar mit einigen Standardbildern).

Bedeutung und Behauptungen
Die Arbeit behauptet, dass P2RAG eine kritische Lücke im Bereich datenschutzfreundlicher RAG schließt: die Unfähigkeit, große $k$ -Werte effizient zu verarbeiten. Die Autoren betonen, dass zwar standardmäßige, nicht-sichere RAG-Systeme einfacher und schneller sind, P2RAG jedoch für hochriskante Bereiche wie Gesundheitswesen, Finanzen und juristische Dienstleistungen unverzichtbar ist, wo Datenschutz eine strikte Anforderung darstellt. Das System ermöglicht diesen Sektoren, große Abfragemengen (die die Genauigkeit von LLMs verbessern) zu nutzen, ohne die Vertraulichkeit proprietärer Datenbanken oder Nutzerabfragen zu gefährden. Die Autoren vermerken bescheiden, dass das System von der Annahme semi-ehrlicher, nicht-kolludierender Server abhängt und dass standardmäßige, nicht-sichere RAG-Systeme weiterhin die Wahl bleiben, wenn Datenschutz nicht kritisch ist.

1. Der alte Weg: Sortieren des gesamten Decks

2. Die P2RAG-Lösung: Das „Raten der Schwelle"-Spiel

3. Geheimnisse sicher halten (Die „Kein-Vertrauen"-Regel)

4. Warum dies wichtig ist (Die Ergebnisse)

Das Fazit

Mehr davon