💻 computer science

OTRO: Oblivious Tokenization Path with Square-Root ORAM

OTRO ist ein effizientes, oblifates Tokenisierungssystem, das für das vertrauliche LLM-Serving entwickelt wurde und Seitenkanal-Lecks aus Speicherzugriffsmustern durch die Nutzung eines Pools von Quadratwurzel-ORAM-Instanzen mit Epoch-basierter Rotation und Chunked-KV-Cache-bewusstem Overlap mildert, wodurch ein nahezu null latenzbedingter Overhead bei signifikanter Reduzierung der beobachtbaren Leckage erreicht wird.

Ursprüngliche Autoren: Jonghyun Lee, Yongqin Wang, Rachit Rajat, Daniel Wong, Mengyuan Li, Murali Annavaram

Veröffentlicht 2026-06-17

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Jonghyun Lee, Yongqin Wang, Rachit Rajat, Daniel Wong, Mengyuan Li, Murali Annavaram

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 senden einen geheimen Brief an einen Freund durch ein hochsicheres, gläsernes Postamt. Das Postamt wird von einer „Trusted Execution Environment“ (TEE) betrieben, die wie ein supergesicherter Tresor ist, in dem Ihr Brief in einem Sicherheitsbehälter eingeschlossen ist, den niemand – nicht einmal der Postamtsleiter – öffnen kann. Sie können die Worte darin nicht lesen.

Das Problem: Der „Token“-Übersetzer
Bevor Ihr Brief verarbeitet werden kann, muss er in einen Code übersetzt werden, den der Computer versteht. Dies geschieht durch ein Werkzeug namens Tokenizer. Betrachten Sie den Tokenizer als einen Übersetzer, der jedes Wort in Ihrem Brief in einem riesigen, festen Wörterbuch nachschlägt, um dessen geheime Codenummer zu finden.

Hier ist der Haken: Obwohl die Worte im Tresor eingeschlossen sind, ist das Muster der Fingerbewegungen des Übersetzers sichtbar.

Wenn Sie „The cat“ schreiben, schlägt der Übersetzer „The“ nach, dann „cat“.
Wenn Sie „The dog“ schreiben, schlägt er „The“ nach, dann „dog“.

Ein hinterlistiger Spion (wie ein böswilliger Cloud-Server-Administrator) kann durch das Beobachten der Fingerbewegungen des Übersetzers genau sehen, welche Seiten des Wörterbuchs berührt werden. Durch das Beobachten der Reihenfolge und Häufigkeit dieser „Nachschläge“ kann der Spion Ihren ursprünglichen Brief rekonstruieren, obwohl er die Worte selbst nie gesehen hat. Dies wird als Side-Channel-Angriff bezeichnet.

Die alte Lösung: Der „PathORAM“-Shuffle
Um den Spion zu stoppen, versuchten Forscher zuvor eine Methode namens PathORAM einzusetzen. Stellen Sie sich dies als eine magische Bibliothek vor, in der der Bibliothekar nicht einfach nur ein Buch holt, sondern jedes Mal, wenn Sie nach einem Buch fragen, jedes einzelne Buch in der gesamten Bibliothek an einen neuen, zufälligen Ort verschiebt. Dies macht es unmöglich zu sagen, welches Buch Sie eigentlich wollten.

Das Ergebnis: Es funktioniert perfekt in Bezug auf die Sicherheit, ist aber unglaublich langsam. Es ist, als würde man nach einem Buch fragen und dann warten müssen, während der Bibliothekar das gesamte Gebäude umräumt. In der Arbeit führte dies dazu, dass das System 13-mal langsamer war, was eine enorme Verzögerung verursachte, bevor die KI überhaupt anfangen konnte, mit Ihnen zu kommunizieren.

Die neue Lösung: OTRO (Das „Rotierende Bibliothekssystem“)
Die Autoren dieser Arbeit, OTRO, erkannten, dass sich das Wörterbuch, das der Übersetzer verwendet, niemals ändert. Die Wörter sind immer dieselben; nur die Reihenfolge, in der der Spion sie beobachtet, ändert sich.

Sie haben ein klügeres System unter Verwendung von drei cleveren Tricks entwickelt:

Der Pool identischer Bibliotheken: Anstatt einer einzigen Bibliothek, die ständig durchgemischt wird, erstellt OTRO einen Pool identischer Bibliotheken. Stellen Sie sich vor, Sie hätten 50 Kopien desselben Wörterbuchs.
Das „Shift“-System: Wenn der Übersetzer Wörter nachschlagen muss, verwendet er Bibliothek #1. Sobald Bibliothek #1 eine bestimmte Anzahl an Nachschlägen (sagen wir 1.000) durchgeführt hat, wechselt der Übersetzer geräuschlos zu Bibliothek #2.
- Die Magie: Während der Übersetzer mit Bibliothek #2 beschäftigt ist, organisiert ein Hintergrund-Mitarbeiter Bibliothek #1 heimlich und langsam im Schatten neu. Da der Mitarbeiter diese Umorganisation durchführt, während der Übersetzer mit der nächsten Bibliothek beschäftigt ist, verlangsamt die Umorganisation den Übersetzer nie.
Das Aufteilen des Briefes: Für sehr lange Briefe unterteilt OTRO den Brief in kleine Stücke. Er übersetzt das erste Stück, während die GPU (das Gehirn der KI) bereits damit beginnt, darüber nachzudenken. Dies ermöglicht es, dass die „Umorganisationsarbeit“ im Hintergrund stattfindet, ohne den Hauptprozess jemals zu stoppen.

Die Ergebnisse

Geschwindigkeit: Da die schwere „Umorganisationsarbeit“ im Hintergrund stattfindet, ist das System fast so schnell wie die ursprüngliche, unsichere Version. Die Arbeit zeigt, dass es das System nur um etwa 4,5 % verlangsamt, was kaum merkbar ist.
Sicherheit: Der Spion kann nicht mehr sehen, welche spezifischen Wörter nachgeschlagen wurden. Alles, was er sehen kann, ist, dass „ein Nachschlag stattfand“. Das Einzige, was der Spion noch erraten kann, ist, wie lang Ihr Brief war (da längere Briefe mehr Nachschläge erfordern), aber er kann nicht erraten, was in dem Brief stand.
Speicher: Es verbraucht etwas mehr Speicher (weniger als ein halbes Gigabyte pro Benutzer), was ein kleiner Preis dafür ist, Ihre Geheimnisse sicher zu halten.

Zusammenfassend
OTRO ist wie das Einstellen eines Teams von Übersetzern, die im Schichtwechsel arbeiten. Während ein Übersetzer arbeitet, räumt ein anderer im Hintergrund heimlich die Bücher um. Auf diese Weise kann der Spion, der die Tür beobachtet, nicht erkennen, welches Buch genommen wurde, aber die Arbeit wird fast augenblicklich erledigt. Es verwandelt ein Sicherheitsproblem, das das System früher 13-mal langsamer machte, in eine Lösung, die nahezu instantan ist.

Technisches Resümee: OTRO – Oblivious Tokenization Path mit Square-Root ORAM

1. Problemstellung

Das Paper identifiziert eine kritische Sicherheitslücke beim vertraulichen Serving von Large Language Models (LLMs): den Tokenizer. Während Trusted Execution Environments (TEEs) wie Intel TDX und NVIDIA GPU TEs die Speicherinhalte und Berechnungen schützen, verbergen sie nicht inhärent die Speicherzugriffsmuster.

Die Schwachstelle: Moderne LLMs verwenden Byte-Pair-Encoding (BPE) Tokenizer, die auf deterministischen, tabellenbasierten Lookups (Vokabular- und Merge-Tabellen) basieren, um Rohtext in Token-IDs umzuwandeln. Da die Abbildung von Tokens auf Speicheradressen nach der Initialisierung feststeht, kann ein Angreifer, der die Hypervisor kontrolliert oder physischen Zugriff auf den Server hat, die DRAM-Zugriffsmuster beobachten (z. B. über Page Faults oder Cache-Seitenkanäle).
Die Konsequenz: Jüngste Arbeiten (TDXRay) haben gezeigt, dass diese Zugriffsmuster eine End-to-End-Rekonstruktion von Nutzer-Prompts mit einer Ähnlichkeit von über 90 % ermöglichen, wodurch der Schutz durch TEEs effektiv umgangen wird.
Die Herausforderung der Abschwächung: Standardmäßige Oblivious RAM (ORAM)-Lösungen, wie etwa PathORAM, führen zu prohibitiven Latenzen. Eine naive Integration von PathORAM erhöht die Time-To-First-Token (TTFT) um etwa das 13-fache, während eine naive Square-Root ORAM (SqrtORAM) aufgrund teurer $O(N \log^2 N)$ Rebuild-Kosten, die alle $\sqrt{N}$ Zugriffe auftreten, um das ~323-fache steigt. Diese Overheads sind für die latenzkritische LLM-Inferenz inakzeptabel.

2. Methodik: OTRO-Architektur

Die Autoren schlagen OTRO (Oblivious Tokenization Path) vor, einen effizienten, oblivious Tokenisierungspfad, der speziell für das LLM-Serving maßgeschneidert ist. Die zentrale Erkenntnis ist, dass Tokenizer-Tabellen während der Inferenz schreibgeschützt (read-only) sind. Diese Eigenschaft ermöglicht es OTRO, die teuren Rebuild-Operationen vom kritischen Zugriffspfad zu entkoppeln.

OTRO erreicht dies durch drei wesentliche Innovationen:

A. Gepoolte SqrtORAM-Replikation

Anstatt einer einzelnen SqrtORAM-Instanz, die nach $\sqrt{N}$ Zugriffen neu aufgebaut werden muss, unterhält OTRO einen Pool aus replizierten, schreibgeschützten SqrtORAM-Instanzen.

Jede Instanz enthält dasselbe Vokabular und dieselben Merge-Daten, jedoch mit einer jeweils unterschiedlichen, zufälligen Permutation.
Da die Daten schreibgeschützt sind, müssen die Instanzen keine Updates abgleichen; sie müssen lediglich neu gemischt (reshuffled) werden, um die Obliviousness aufrechtzuerhalten.
Während eine Instanz neu aufgebaut wird, können andere Anfragen weiterhin bedienen.

B. Epochenbasierte Rotation und Padding

OTRO implementiert eine epochenbasierte Rotationspolitik, um den Pool zu verwalten:

Rotation: Jede Instanz bedient genau $\sqrt{N}$ Zugriffe (eine Epoche). Sobald das Limit erreicht ist, wird die Instanz für einen asynchronen Hintergrund-Rebuild markiert, und das System rotiert zu einer frischen Instanz.
Padding: Um zu verhindern, dass die exakte Anzahl der Zugriffe innerhalb einer Epoche Informationen preisgibt, ergänzt OTRO jede Epoche mit Dummy-Zugriffen, bis die $\sqrt{N}$ -Grenze erreicht ist. Dies stellt sicher, dass das beobachtbare Transkript nur die Epochenanzahl (und damit die grobe Zugriffshäufigkeit) offenbart, aber nicht die präzise Anzahl der Lookups.
Sicherheit: Die Instanzwahl ist eine deterministische Funktion der globalen Zugriffszahl, unabhängig von der spezifisch aufgerufenen logischen Adresse, was die Ununterscheidbarkeit der Zugriffsmuster gewährleistet.

C. Chunked Tokenization mit KV-Cache-Bewusstsein

Um die benötigte Poolgröße zu minimieren, um Stalls zu vermeiden und die Rebuild-Latenz zu verbergen, führt OTRO die Chunked Tokenization ein:

Lange Input-Prompts werden an vordefinierten Tokenisierungsgrenzen (whitespace-getrennte Wörter) in kleinere Chunks aufgeteilt.
Die Tokenisierung eines Chunks wird mit der Prefill-Phase der GPU verzahnt.
Das System ist so abgestimmt, dass die Zeit, die die GPU benötigt, um einen Chunk zu verarbeiten ( $T_{gpu, prefill}$ ), größer ist als die Zeit, die für den Rebuild einer SqrtORAM-Instanz benötigt wird ( $T_{reshuffle}$ ).
Diese Überlappung ermöglicht es, Rebuilds im Hintergrund während der GPU-Berechnung durchzuführen, wodurch die Rebuild-Kosten amortisiert und die Anzahl der benötigten SqrtORAM-Instanzen im Pool reduziert werden.

D. Detokenisierung

OTRO wendet den ORAM-Schutz auch auf den Detokenisierungspfad an (Konvertierung von Token-IDs zurück in Text). Aufgrund der Natur der Decode-Phase (bei der Tokens langsam über die Zeit generiert werden) reicht ein kleiner Pool (z. B. 2 Instanzen) aus, um die Rebuilds mit den Decode-Kerneln zu überlappen und die Latenz zu verbergen.

3. Wesentliche Beiträge

Kostencharakterisierung: Die Autoren zeigen, dass, während naive ORAM-Verteidigungen prohibitiv sind (13×–323× Verlangsamung), die Rebuild-Kosten der primäre Flaschenhals sind. Durch die Entfernung der Rebuilds aus dem kritischen Pfad erreicht OTRO nahezu die ungeschützte Baseline mit weniger als 2,4× Overhead.
Oblivious Architektur: Eine neuartige Architektur, die einen Pool aus schreibgeschützten SqrtORAM-Instanzen, epochenbasierte Rotation und Zugriffszahl-Padding nutzt, um Rebuilds aus dem kritischen Pfad zu eliminieren.
Latenzbewusste Integration: Die Integration von Chunked Tokenization mit GPU-Prefill und KV-Cache-Mechanismen, um CPU-seitige Rebuilds mit der GPU-Berechnung zu überlappen und so den Speicherbedarf sowie die Instanzanzahl zu minimieren.
End-to-End Prototyp: Implementierung von OTRO innerhalb von HuggingFace Tokenizers und nano-vLLM, ausgeführt in einer TDX-fähigen Confidential Virtual Machine (CVM) mit einer NVIDIA H100 GPU.
Reduktion der Leakage: Ein formaler Beweis zeigt, dass die Zugriffsmuster von OTRO nichts über die berührten Tabelleneinträge verraten. Mit Padding ist die einzige unvermeidbare Leakage die Länge des Input-Prompts (Byte-Länge), was bei jedem praktischen ORAM-Design inhärent ist.

4. Experimentelle Ergebnisse

Das System wurde mit Llama-3.1, Qwen3, Gemma-3 und Phi-3 Modellen unter Verwendung einer Intel Xeon Gold CPU und einer NVIDIA H100 GPU evaluiert.

Latenz (TTFT): OTRO begrenzt den TTFT-Overhead auf maximal 4,5 % im Vergleich zur ungeschützten Baseline.
- PathORAM erhöhte die TTFT um ~1,48×.
- Naives SqrtORAM erhöhte die TTFT um ~11,12×.
- OTRO (mit Chunking) erreicht nahezu das "ideale" SqrtORAM-Szenario (keine Rebuild-Strafen) und hält die durch den Tokenizer verursachte Latenz unter 10 % der gesamten TTFT.
Speicher-Overhead: OTRO fügt pro Client weniger als 0,5 GB Speicher-Overhead hinzu (z. B. ~286 MB für Llama-3.1 mit 48 Instanzen). Dies ist signifikant niedriger als der Overhead, der für PathORAM in einigen Konfigurationen erforderlich ist, und ermöglicht es einer 256 GB CVM, zehntausende gleichzeitige Clients zu unterstützen.
Initialisierung: Die Initialisierungskosten steigen je nach Modell um 35–350 %, aber da dies ein einmaliger Kostenfaktor pro Modell-Load ist, wird dies nicht als System-Flaschenhals betrachtet.
Leakage-Analyse:
- Ohne ORAM kann ein Angreifer Prompts mit ~0 Bits Restunsicherheit rekonstruieren.
- Mit OTRO (oh:ne Padding) beträgt die Restunsicherheit 1,60 Bits.
- Mit OTRO (mit Zugriffszahl-Padding) steigt die Restunsicherheit auf 5,49 Bits, was 38,4 % der ursprünglichen Prompt-Entropie wiederherstellt. Die verbleibende Leakage resultiert primär aus der unvermeidbaren Korrelation zwischen der Byte-Länge des Inputs und der Zugriffszahl.

5. Bedeutung und Ansprüche

Das Paper behauptet, dass OTRO einen praktikablen Weg zu End-to-End-Vertraulichkeit in produktionsreifen LLM-Serving-Stacks bietet. Es adresset eine spezifische, hochgradig aussagekräftige Seitenkanal-Schwachstelle (Tokenizer-Zugriffsmuster), die trotz Standard-TEE-Schutzmaßnahmen bestehen bleibt.

Praktikabilität: Im Gegensatz zu früheren theoretischen ORAM-Lösungen oder solchen, die für andere Bedrohungsmodelle entwickelt wurden (z. B. SGX mit Speicherbeschränkungen), ist OTRO speziell auf die latenzsensible, schreibgeschützte Natur der LLM-Tokenisierung in modernen CVMs mit GPU-Unterstützung ausgelegt.
Trade-off zwischen Sicherheit und Leistung: Die Arbeit demonstriert, dass es möglich ist, eine starke Zugriffsmuster-Vertraulichkeit (Verbergen dessen, welche Tokens aufgerufen werden) mit minimalem Performance-Impact (<5 % TTFT-Overhead) zu erreichen – ein Kompromiss, der zuvor als prohibitiv galt.
Geltungsbereich: Die Autoren stellen explizit klar, dass OTRO die Speicherzugriffsmuster der Tokenizer-Tabellen schützt. Es erhebt nicht den Anspruch, alle Seitenkanäle (z. B. zeitliche Variabilität durch spezifische Codemuster) zu eliminieren oder die Leakage der Input-Länge zu verhindern, welche als unvermeidbare Basis in praktischen ORAM-Implementierungen behandelt wird.

Zusammenfassend transformiert OTRO die burstartigen, kritischen Rebuild-Kosten von SqrtORAM in Hintergrundaufgaben durch Replikation und Scheduling, wodurch eine sichere, latenzarme LLM-Inferenz gegenüber einem mächtigen, privilegierten Angreifer ermöglicht wird.