💻 computer science

OTRO: Oblivious Tokenization Path with Square-Root ORAM

OTRO est un système de tokenisation efficace et inviolable conçu pour le service de LLM confidentiels qui atténue les fuites par canaux auxiliaires provenant des schémas d'accès à la mémoire en exploitant un pool d'instances ORAM de racine carrée avec une rotation par époque et un chevauchement par blocs sensible au cache KV, atteignant un surcoût de latence quasi nul tout en réduisant considérablement les fuites observables.

Auteurs originaux : Jonghyun Lee, Yongqin Wang, Rachit Rajat, Daniel Wong, Mengyuan Li, Murali Annavaram

Publié 2026-06-17

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Jonghyun Lee, Yongqin Wang, Rachit Rajat, Daniel Wong, Mengyuan Li, Murali Annavaram

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous envoyez une lettre secrète à un ami via une poste aux parois de verre hautement sécurisée. La poste est gérée par un « Environnement d'Exécution Sécurisé » (TEE), qui est comme un coffre-fort ultra-sécurisé où votre lettre est enfermée dans une boîte de sécurité que personne — pas même le directeur de la poste — ne peut ouvrir. Ils ne peuvent pas lire les mots à l'intérieur.

Le Problème : Le Traducteur de « Jeton »
Avant que votre lettre ne puisse être traitée, elle doit être traduite en un code que l'ordinateur comprend. Cela est fait par un outil appelé Tokenizer (un tokenizer). Considérez le Tokenizer comme un traducteur qui cherche chaque mot de votre lettre dans un dictionnaire géant et fixe pour trouver son numéro de code secret.

Voici le piège : même si les mots sont verrouillés dans le coffre, le schéma des mouvements de doigts du traducteur est visible.

Si vous écrivez « Le chat », le traducteur cherche « Le », puis « chat ».
Si vous écrivez « Le chien », le traducteur cherche « Le », puis « chien ».

Un espion rusé (comme un administrateur de serveur cloud malveillant) observant les mouvements de doigts du traducteur peut reconstruire votre lettre originale, même s'il n'a jamais vu les mots eux-mêmes. En observant l'ordre et la fréquence de ces « recherches », l'espion peut reconstituer votre lettre originale. C'est ce qu'on appelle une attaque par canal auxiliaire (side-channel attack).

L'Ancienne Solution : Le Mélange « PathORAM »
Pour arrêter l'espion, des chercheurs ont précédemment tenté d'utiliser une méthode appelée PathORAM. Imaginez cela comme une bibliothèque magique où, chaque fois que vous demandez un livre, le bibliothécaire ne se contente pas de l'aller chercher ; il mélange également chaque livre de toute la bibliothèque pour les placer à un nouvel endroit aléatoire. Cela rend impossible de savoir quel livre vous vouliez réellement.

Le Résultat : Cela fonctionne parfaitement pour la sécurité, mais c'est incroyablement lent. C'est comme demander un livre et devoir attendre que le bibliothécaire réorganise tout le bâtiment. Dans l'article, cela a rendu le système 13 fois plus lent, provoquant un énorme retard avant que l'IA ne puisse même commencer à vous parler.

La Nouvelle Solution : OTRO (Le Système de la « Bibliothèque Rotative »)
Les auteurs de cet article, OTRO, ont réalisé que le dictionnaire utilisé par le traducteur ne change jamais. Les mots sont toujours les mêmes ; seul l'ordre dans lequel l'espion les observe change.

Ils ont construit un système plus intelligent utilisant trois astuces ingénieuses :

Le Pool de Bibliothèques Identiques : Au lieu d'une seule bibliothèque qui est constamment mélangée, OTRO crée un pool de bibliothèques identiques. Imaginez avoir 50 copies du même dictionnaire.
Le Système de « Décalage » : Lorsque le traducteur doit chercher des mots, il utilise la Bibliothèque n°1. Une fois que la Bibliothèque n°1 a été utilisée un nombre spécifique de fois (disons, 1 000 recherches), le traducteur passe discrètement à la Bibliothèque n°2.
- La Magie : Pendant que le traducteur est occupé à utiliser la Bibliothèque n°2, un travailleur en arrière-plan réorganise secrètement et lentement la Bibliothèque n°1 dans l'ombre. Parce que le travailleur effectue cette tâche pendant que le traducteur est occupé avec la bibliothèque suivante, la réorganisation ne ralentit jamais le traducteur.
Le Découpage de la Lettre : Pour les lettres très longues, OTRO découpe la lettre en petits morceaux. Il traduit la première partie pendant que le GPU (le cerveau de l'IA) commence déjà à réfléchir à celle-ci. Cela permet au travail de « réorganisation » de se faire en arrière-plan sans jamais interrompre le processus principal.

Les Résultats

Vitesse : Parce que le travail lourd de « réorganisation » se déroule en arrière-plan, le système est presque aussi rapide que la version originale non sécurisée. L'article montre qu'il ne ralentit les choses que d'environ 4,5 %, ce qui est à peine perceptible.
Sécurité : L'espion ne peut plus voir quels mots spécifiques ont été recherchés. Tout ce qu'il peut voir, c'est qu'« une recherche a eu lieu ». La seule chose que l'espion peut encore deviner est la longueur de votre lettre (car les lettres plus longues nécessitent plus de recherches), mais il ne peut pas deviner le contenu de la lettre.
Mémoire : Il utilise un peu plus de mémoire (moins d'un demi-gigaoctet par utilisateur), ce qui est un petit prix à payer pour garder vos secrets en sécurité.

En Résumé
OTRO est comme embaucher une équipe de traducteurs qui tournent par roulement. Pendant qu'un traducteur travaille, un autre réorganise discrètement les livres en arrière-plan. De cette façon, l'espion qui surveille la porte ne peut pas savoir quel livre a été choisi, mais le travail est accompli presque instantanément. Cela transforme un problème de sécurité qui rendait le système 13 fois plus lent en une solution qui est presque instantanée.

Résumé Technique : OTRO – Chemin de Tokenisation Oblivieux avec SqrtORAM

1. Énoncé du Problème

L'article identifie une faille de sécurité critique dans le service de modèles de langage (LLM) confidentiels : le tokenizer (le jetoniseur). Bien que les environnements d'exécution de confiance (TEE) tels qu'Intel TDX et les GPU NVIDIA TEE protègent le contenu de la mémoire et les calculs, ils ne cachent pas intrinsèquement les schémas d'accès à la mémoire.

La Vulnérabilité : Les LLM modernes utilisent des tokeniseurs de type Byte-Pair Encoding (BPE), qui reposent sur des recherches déterministes basées sur des tables (vocabulaire et tables de fusion) pour convertir le texte brut en identifiants de jetons (token IDs). Comme la correspondance entre les jetons et les adresses mémoire est fixe après l'initialisation, un adversaire contrôlant l'hyperviseur ou ayant un accès physique au serveur peut observer les schémas d'accès à la DRAM (via des fautes de pages ou des canaux auxiliaires de cache).
La Conséquence : Des travaux récents (TDXRay) ont démontré que ces schémas d'accès permettent la reconstruction de bout en bout des prompts de l'utilisateur avec une similitude de plus de 90 %, contournant ainsi efficacement les protections des TEE.
Le Défi de l'Atténuation : Les solutions d'Oblivious RAM (ORAM) standards, telles que PathORAM, introduisent une latence prohibitive. Une intégration naïve de PathORAM augmente le temps de premier jeton (TTFT) d'environ 13×, tandis qu'une intégration naïve de SqrtORAM (Square-Root ORAM) l'augmente d'environ 323× en raison des coûts de reconstruction coûteux de l'ordre de $O(N \log^2 N)$ se produisant tous les $\sqrt{N}$ accès. Ces surcoûts sont inacceptables pour l'inférence de LLM, qui est sensible à la latence.

2. Méthodologie : Architecture OTRO

Les auteurs proposent OTRO (Oblivious Tokenization Path), un chemin de tokenisation efficace et oblivieux, adapté au service de LLM. L'idée centrale est que les tables du tokenizer sont en lecture seule pendant l'inférence. Cette propriété permet à OTRO de découpler les opérations de reconstruction coûteuses du chemin d'accès critique.

OTRO y parvient grâce à trois innovations clés :

A. Réplication SqrtORAM par Pool

Au lieu d'une instance unique de SqrtORAM qui doit être reconstruite après $\sqrt{N}$ accès, OTRO maintient un pool d'instances SqrtORAM répliquées et en lecture seule.

Chaque instance détient le même vocabulaire et les mêmes données de fusion, mais avec une permutation aléatoire distincte.
Puisque les données sont en lecture seule, les instances n'ont pas besoin de réconcilier les mises à jour ; elles doivent seulement être redistribuées pour maintenir l'obliviosité.
Pendant qu'une instance est en cours de reconstruction, les autres continuent de servir les requêtes.

B. Rotation par Époque et Padding (Remplissage)

OTRO implémente une politique de rotation par époque pour gérer le pool :

Rotation : Chaque instance sert exactement $\sqrt{N}$ accès (une époque). Une fois la limite atteinte, l'instance est marquée pour une reconstruction asynchrone en arrière-plan, et le système passe à une nouvelle instance.
Padding : Pour éviter que le nombre exact d'accès au sein d'une époque ne révèle des informations, OTRO complète chaque époque par des accès fictifs (dummy accesses) pour atteindre la limite de $\sqrt{N}$ . Cela garantit que le transcript observable ne révèle que le nombre d'époques (et donc le nombre grossier d'accès), et non le nombre précis de recherches.
Sécurité : La sélection de l'instance est une fonction déterministe du nombre total d'accès, indépendante de l'adresse logique spécifique accédée, garantissant l'indistinguabilité des schémas d'accès.

C. Tokenisation par Blocs avec Sensibilité au KV-Cache

Pour minimiser la taille du pool requise afin d'éviter les blocages et de masquer la latence de reconstruction, OTRO introduit la tokenisation par blocs (chunked tokenization) :

Les longs prompts d'entrée sont divisés en blocs plus petits aux limites de pré-tokenisation (mots délimités par des espaces).
La tokenisation d'un bloc est entrelacée avec la phase de prefill du GPU.
Le système est réglé de telle sorte que le temps nécessaire au GPU pour traiter un bloc ( $T_{gpu, prefill}$ ) est supérieur au temps nécessaire pour reconstruire une instance de SqrtORAM ( $T_{reshuffle}$ ).
Ce chevauchement permet aux reconstructions de se produire en arrière-plan pendant que le GPU calcule, amortissant ainsi le coût de reconstruction et réduisant le nombre d'instances SqrtORAM nécessaires dans le pool.

D. Détokenisation

OTRO applique également la protection ORAM au chemin de détokenisation (conversion des ID de jetons en texte). En raison de la nature de l'étape de décodage (où les jetons sont générés lentement au fil du temps), un petit pool (par exemple, 2 instances) est suffisant pour superposer les reconstructions avec les noyaux (kernels) de décodage, masquant ainsi la latence.

3. Contributions Clés

Caractérisation des Coûts : Les auteurs démontrent que si les défenses ORAM naïves sont prohibitives (ralentissement de 13× à 323×), le coût de reconstruction est le principal goulot d'étranglement. En retirant les reconstructions du chemin critique, OTRO suit la ligne de base non protégée avec un surcoût de moins de 2,4×.
Architecture Oblivieuse : Une architecture novatrice utilisant un pool d'instances SqrtORAM en lecture seule, une rotation par époque et un padding du nombre d'accès pour éliminer les reconstructions du chemin critique.
Intégration Sensible à la Latence : L'intégration de la tokenisation par blocs avec le prefill du GPU et les mécanismes de KV-cache pour superposer les reconstructions côté CPU avec le calcul GPU, minimisant l'empreinte mémoire et le nombre d'instances.
Prototype de Bout en Bout : Implémentation de OTRO au sein de HuggingFace Tokenizers et nano-vLLM, s'exécutant dans une machine virtuelle confidentielle (CVM) dotée de TDX avec un GPU NVIDIA H100.
Réduction de la Fuite d'Information : Preuve formelle que les schémas d'accès de OTRO ne révèlent rien sur les entrées spécifiques touchées. Avec le padding, la seule fuite inévitable est la longueur du prompt d'entrée (longueur en octets), ce qui est inhérent à toute conception ORAM pratique.

4. Résultats Expérimentaux

Le système a été évalué sur les modèles Llama-3.1, Qwen3, Gemma-3 et Phi-3 en utilisant un processeur Intel Xeon Gold et un GPU NVIDIA H100.

Latence (TTFT) : OTRO limite le surcoût du TTFT à au plus 4,5 % par rapport à la ligne de base non protégée.
- PathORAM a augmenté le TTFT d'environ 1,48×.
- Un SqrtORAM naïf a augmenté le TT passé par environ 11,12×.
- OTRO (avec chunking) performe près du scénario SqrtORAM "idéal" (sans pénalité de reconstruction), maintenant la latence induite par le tokenizer sous les 10 % du TTFT total.
Surcoût Mémoire : OTRO ajoute moins de 0,5 Go de surcoût mémoire par client (par exemple, ~286 Mo pour Llama-3.1 avec 48 instances). C'est nettement inférieur au surcoût requis par PathORAM dans certaines configurations, permettant à une CVM de 256 Go de supporter des dizaines de clients simultanés.
Initialisation : Les coûts d'initialisation augmentent de 35 à 350 % selon le modèle, mais comme il s'agit d'un coût unique par chargement de modèle, cela n'est pas considéré comme un goulot d'étranglement du système.
Analyse de la Fuite :
- Sans ORAM, un adversaire peut reconstruire les prompts avec environ 0 bit d'incertitude résiduelle.
- Avec OTRO (sans padding), l'incertitude résiduelle est de 1,60 bit.
- Avec OTRO (avec padding du nombre d'accès), l'incertitude résiduelle monte à 5,49 bits, récupérant 38,4 % de l'entropie originale du prompt. La fuite restante est principalement due à la corrélation inévitable entre la longueur en octets de l'entrée et le nombre d'accès.

5. Signification et Revendications

L'article affirme que OTRO offre une voie viable vers la confidentialité de bout en bout dans les piles de service de LLM en production. Il traite un canal auxiliaire spécifique et de haute fidélité (les schémas d'accès au tokenizer) qui survit aux protections TEE standards.

Praticité : Contrairement aux solutions ORAM théoriques précédentes ou conçues pour des modèles de menaces différents (comme SGX avec des contraintes de mémoire), OTRO est spécifiquement conçu pour la nature de lecture seule et sensible à la latence de la tokenisation de LLM dans les CVM modernes avec support GPU.
Compromis Sécurité/Performance : Ce travail démontre qu'il est possible d'obtenir une forte confidentialité des schémas d'accès (cacher quels jetons sont accédés) avec un impact de performance négligeable (<5 % de surcoût TTFT), un compromis qui était auparavant jugé prohibitif.
Portée : Les auteurs déclarent explicitement que OTRO protège les schémas d'accès à la mémoire des tables du tokenizer. Ils ne prétendent pas éliminer tous les canaux auxiliaires (comme la variabilité de temps provenant de schémas de code spécifiques) ou protéger contre la fuite de la longueur d'entrée, qui est traitée comme une base inévitable dans les déploiements ORAM pratiques.

En résumé, OTRO transforme le coût de reconstruction par rafales et critique de SqrtORAM en un travail d'arrière-plan grâce à la réplication et à l'ordonnancement, permettant une inférence de LLM sécurisée et à faible latence face à un adversaire privilégié et puissant.