技術要約: OTRO – Square-Root ORAMを用いた不可視トークナイゼーション・パス

1. 問題提起

本論文は、機密性の高い大規模言語モデル（LLM）サービングにおける重大なセキュリティ上の欠陥、すなわちトークナイザーを特定している。Intel TDXやNVIDIA GPU TEEのような信頼実行環境（TEE）は、メモリの内容や計算を保護するが、メモリへのアクセスパターンを本質的に隠蔽するものではない。

• 脆弱性: 現代のLLMはバイトペアエンコーディング（BPA）トークナイザーを使用しており、これは生のテキストをトークンIDに変換するために、決定論的なテーブル駆動型のルックアップ（語彙およびマージテーブル）に依存している。トークンからメモリのアドレスへのマッピングは初期化後に固定されるため、ハイパーバイザーを制御する攻撃者やサーバーへの物理的アクセスを持つ攻撃者は、DRAMへのアクセスパターン（ページフォールトやキャッシュサイドチャネル経由）を観察することができる。
• 結果: 最近の研究（TDXRay）は、これらのアクセスパターンによって、ユーザーのプロンプトを90%以上の類似度でエンドツーエンドで再構成できることを示した。これは、TEEによる保護を事実上無効化するものである。
• 緩和策の課題: 標準的なOblivious RAM（ORAM）ソリューション、例えばPathORAMは、法外なレイテンシを導入する。PathORAMを素朴に統合すると、Time-To-First-Token（TTFT）が約13倍増加し、素朴なSquare-Root ORAM（SqrtORAM）では、$\sqrt{N}$ 回のアクセスのたびに発生する高価な $O(N \log^2 N)$ のリビルド・コストにより、TTFTが約323倍増加する。これらのオーバーヘッドは、レイテンシが極めて重要なLLM推論においては受け入れがたいものである。

2. 手法: OTRO アーキテクチャ

著者らは、LLMサービング向けに最適化された効率的な不可視トークナイゼーション・パスである OTRO (Oblivious Tokenization Path) を提案する。核心となる洞察は、トークナイザのテーブルは推論中、**読み取り専用（read-only）**であるという点である。この特性により、OTROは高価なリビルド操作をクリティカルパスから切り離すことが可能になる。

OTROは、以下の3つの主要な革新技術を通じてこれを実現している。

A. プール化された SqrtORAM の複製

$\sqrt{N}$ 回のアクセスの後にリビルドが必要となる単一の SqrtORAM インスタンスの代わりに、OTROは複製された読み取り専用の SqrtORAM インスタンスのプールを維持する。

• 各インスタンスは同じ語彙とマージデータを持つが、それぞれ異なるランダムな置換（permutation）を持つ。
• データは読み取り専用であるため、インスタンス間で更新を調整する必要はなく、不可視性を維持するためにシャッフル（reshuffle）を行うだけでよい。
• あるインスタンスがリビルドされている間も、他のインスタンスはリクエストを処理し続けることができる。

B. エポックベースのローテーションとパディング

OTROは、プールを管理するためにエポックベースのローテーション・ポリシーを実装している：

• ローテーション: 各インスタンスは正確に $\sqrt{N}$ 回のアクセス（1エポック）を処理する。制限に達すると、そのインスタンスは非同期のバックグラウンド・リビルド用にマークされ、システムは新しいインスタンスへとローテーションする。
• パディング: エポック内の正確なアクセス数が情報を漏洩させるのを防ぐため、OTROは各エポックをダミーアクセスで補完して $\sqrt{N}$ の境界に到達させる。これにより、観測可能なトランスクリプトはエポック数（したがって粗いアクセス数）のみを明らかにし、正確なルックアップ回数は明らかにされない。
• セキュリティ: インスタンスの選択は、アクセスされている特定の論理アドレスには依存せず、グローバルなアクセス数の決定論的な関数であるため、アクセスパターンの不可識別性が保証される。

C. KVキャッシュを考慮したチャンク化トークナイゼーション

リビルドによる停止を回避し、リビルドのレイテンシを隠蔽するために必要なプールのサイズを最小化するため、OTROはチャンク化トークナイゼーションを導入している：

• 長い入力プロンプトは、事前トークナイゼーションの境界（空白区切りの単語）で小さなチャンクに分割される。
• チャンクのトークナイゼーションは、GPUの**プリフィル（prefill）**フェーズとインターリーブ（交互に実行）される。
• システムは、GPUがチャンクを処理する時間（$T_{gpu, prefill}$）が、SqrtORAMインスタンスをリビルドする時間（$T_{reshuffle}$）よりも大きくなるようにチューニングされている。
• このオーバーラップにより、GPUが計算を行っている間にバックグラウンドでリビルドを実行することができ、リビルド・コストを効果的に償却し、プールに必要なSqrtORAMインスタンスの数を最小限に抑えることができる。

D. デトークナイゼーション

OTROは、デトークナイゼーション・パス（トークンIDをテキストに変換する工程）にもORAM保護を適用する。デコード段階の性質（トークンが時間をかけてゆっくりと生成されること）から、リビルドをデコードカーネルとオーバーラップさせるには、小さなプール（例：2つのインスタンス）で十分である。

3. 主な貢献

1. コスト特性の解明: 著者らは、素朴なORAM防御が極めて困難である（13倍〜323倍の低速化）一方で、リビルド・コストが主要なボトルネックであることを示している。リビルドをクリティカルパスから排除することで、OTROは保護されていないベースラインに近い性能を実現している。
2. 不可視アーキテクチャ: 読み取り専用の SqrtORAM インスタンスのプール、エポックベースのローテーション、およびアクセス数パディングを利用して、リビルドをクリティカルパスから排除する新しいアーキテクチャ。
3. レイテンシを考慮した統合: チャンク化トークナイゼーションをGPUのプリフィルおよびKVキャッシュ・メカニズムと統合し、CPU側のリビルドをGPU計算とオーバーラップさせることで、メモリフットプリントとインスタンス数を最小化する。
4. エンドツーエンドのプロトタイプ: HuggingFace Tokenizersおよびnano-vLLM内にOTROを実装し、Intel TDX対応の機密仮想マシン（CVM）およびNVIDIA H100 GPU上で動作させた。
5. 漏洩の低減: OTROのアクセスパターンが、接触した特定のテーブルのエントリについて何も明らかにしないことを形式的に証明した。パディングを用いることで、避けられない漏洩は入力プロンプトの長さ（バイト長）のみであり、これは実用的なあらゆるORAM設計において固有のものである。

4. 実験結果

システムは、Llama-3.1、Qwen3、Gemma-3、Phi-3モデルを用い、Intel Xeon Gold CPUおよびNVIDIA H100 GPUを使用して評価された。

• レイテンシ (TTFT): OTROは、保護されていないベースラインと比較して、TTFTのオーバーヘッドを最大**4.5%**に抑える。
  • PathORAMはTTFTを約1.48倍に増加させた。
  • 素朴な SqrtORAM はTTFTを約11.12倍に増加させた。
  • チャンキングを用いたOTROは、「理想的な」SqrtORAMシナリオ（リビルド・ペナルティなし）に近い性能を示し、トークナイザーに起因するレイテンシを総TTFTの10%未満に抑えている。
• メモリ・オーバーヘッド: OTROはクライアントあたり0.5 GB未満のメモリ・オーバーヘッドを追加する（例：Llama-3.1で48インスタンスの場合、約286 MB）。これは、いくつかの構成におけるPathORAMのオーバーヘッドよりも大幅に低く、256 GBのCVMで数十の同時クライアントをサポートすることを可能にする。
• 初期化: 初期化コストはモデルに応じて35〜350%増加するが、これはモデルロードごとの一度限りのコストであるため、システムのボトルネックとはみなされない。
• 漏洩分析:
  • ORAMがない場合、攻撃者は残留不確実性がほぼ0ビットの状態でプロンプトを再構成できる。
  • OTRO（パディングなし）の場合、残留不確実性は1.60ビットである。
  • OTRO（アクセス数パディングあり）の場合、残留不確実性は5.49ビットに上昇し、元のプロンプト・エントロピーの38.4%を回復する。残りの漏洩は、主に、入力バイト長とアクセス数の間の避けられない相関関係によるものである。

5. 重要性と主張

本論文は、OTROがプロダクション環境のLLMサービング・スタックにおいて、エンドツーエンドの機密性への実行可能な道筋を提供するものであると主張している。これは、標準的なTEE保護を回避してしまう特定の、高精度なサイドチャネル（トークナイザーのアクセスパターン）に対処するものである。

• 実用性: 以前の理論的なORAMソリューションや、異なる脅威モデル（メモリ制約のあるSGXなど）向けに設計されたものとは異なり、OTROは、GPUサポートを備えた現代のCVMにおける、レイテンシに敏感で読み取り専用の性質を持つLLMトークナイゼーションに特化して設計されている。
• セキュリティとパフォーマンスのトレードオフ: 本研究は、強力なアクセスパターンの機密性（どのトークンがアクセスされたかを隠す）を、これまで不可能と考えられていた極めて低いパフォーマンスへの影響（TTFTオーバーヘッド5%未満）で達成できることを示している。
• 範囲: 著者らは、OTROがトークナイザー・テーブルのメモリ・アクセス・パターンを保護することを明示している。すべてのサイドチャネル（例：特定のコードパターンからのタイミングの変動）を排除することや、入力長による漏洩を防ぐことを主張しているわけではなく、それは実用的なORAM展開における避けられないベースラインとして扱われている。

要約すると、OTROは、複製とスケジューリングを通じて、突発的でクリティカルパスとなるリビルド・コストをバックグラウンド作業へと変換し、強力で特権的な攻撃者が存在する環境下でも、低レイテンシで安全なLLM推論を可能にする。