忘却 RAM(ORAM)とアクセスパターン秘匿

解きたい問題：暗号化しても「どこを読んだか」が漏れる

データを暗号化すれば安全、という直感には大きな穴があります。暗号化が隠すのは各ブロックの中身（plaintext）だけで、どのアドレスを、いつ、どの順で読み書きしたかというアクセスパターンは隠しません。サーバーやクラウド事業者、あるいは同じ物理マシンに同居する攻撃者は、暗号文を一切復号できなくても、この物理アクセスの足跡を観測できます。

この足跡は驚くほど多くを語ります。暗号化された検索インデックスに対し「ある検索語でどのブロック群が触られるか」を観測し続ければ、頻度や共起の統計から検索語そのものを高確率で復元できます（access-pattern leakage 攻撃、暗号化検索の代表的破綻）。アルゴリズムの分岐や配列添字が秘密値に依存していれば、メモリアクセス列から秘密鍵が漏れます。これは サイドチャネル攻撃 のうちキャッシュ系・メモリ系が突くまさにその漏洩で、AES の T-table 実装が鍵を漏らした古典例もアクセスパターン依存が原因です。

厄介なのは、この漏洩が暗号化やハードウェア隔離では塞げない点です。TEE とセキュアエンクレーブ はメモリ内容を暗号化しますが、ページフォルトやキャッシュ経由でエンクレーブのアクセス列が外から観測可能で、controlled-channel 攻撃が成立します。**忘却 RAM（Oblivious RAM, ORAM）**は、この「アクセスパターンそのものを秘匿する」ことを正面から扱う技術です。

ORAM の安全性定義：アクセス列が中身から独立であること

ORAM の目標は厳密に定義できます。クライアントが行いたい論理アクセス列を (op1, op2, …, opM)（各 op は read(addr) または write(addr, data)）とします。ORAM 方式が安全であるとは、任意の二つの同じ長さの論理アクセス列が、サーバーから見て計算量的に区別できない物理アクセス列を生むことです。

論理列 A = read(5), read(5), read(5)         # 同じ番地を 3 回
論理列 B = read(2), write(7,x), read(99)     # 全部バラバラ
  ⇒ ORAM 通過後、サーバーが観測する物理アクセス列の分布は
     A 由来でも B 由来でも区別がつかない（statistically/computationally close）

ここから ORAM が満たすべき二条件が導けます。第一に、論理アドレスと物理アクセス位置の対応が毎回変わること（同じ番地を二度読んでも、観測される物理位置が前回と相関してはならない）。第二に、各操作が読みか書きかも漏らさないこと（読みでも必ず書き戻し、書きでも必ず読む）。

素朴な解と Square-Root ORAM

最も素朴な ORAM は毎回ストレージ全体を線形走査することです。どの 1 ブロックが欲しくても N ブロック全部を読めば、触った位置は常に全体で一定なので何も漏れません。しかし 1 アクセスに O(N) の帯域がかかり実用外です。ORAM 研究の歴史は、この O(N) をいかに下げるかの競争でした。

Goldreich と Ostrovsky による古典的な Square-Root ORAM は O(√N) 程度のコストに下げました。N ブロックに √N 個のダミーを足してランダム置換で並べ、√N 個の小さな**シェルター（stash）**を別に持ちます。アクセスのたびにシェルターを全走査し、目的ブロックがそこになければ本体の該当位置を、あれば未使用のダミー位置を読む（どちらに見えるかを揃える）。読んだブロックはシェルターに移し、√N 回ごとに全体を再シャッフルします。この「ダミーを混ぜて毎回違う位置を読み、定期的に再配置する」発想が、後続のすべての ORAM に受け継がれる核です。

Path ORAM：二分木で対数コストを実現する

実務でデファクトとなったのが Path ORAM（Stefanov ら, 2013）です。単純で、対数コストの下界にほぼ届き、証明も明快です。構造は次の通りです。

• サーバー側ストレージを二分木にする。木の高さは約 log N、ノード数は N 程度。各ノードは数ブロック（典型的に Z = 4）を入れられる**バケット（bucket）**で、空きはダミーブロックで埋める（暗号文上は本物と区別不能）。
• クライアントは小さな**ポジションマップ（position map）**を持つ。これは「論理ブロック a → どのリーフ x に紐づくか」の対応表。
• クライアントは小さなスタッシュ（stash）（あふれた数ブロックを一時保持する領域）を持つ。

不変条件はただ一つ――論理ブロック a は、ポジションマップが指すリーフ x への、根からの経路（path）上のいずれかのバケット、またはスタッシュに必ず存在する。木の経路は根から一意なので、a を探すには「リーフ x への経路を根からたどる log N 個のバケットを全部読む」だけで足ります。

Path ORAM の 1 アクセス access(op, a):
  1. x  = PositionMap[a]            # 現在 a が紐づくリーフ
  2. PositionMap[a] = UniformRandom(0 .. L-1)   # ★即座に新しいリーフへ乱択し直す
  3. read_path(x)  → スタッシュへ    # リーフ x への経路上の全バケットを読み、復号して stash に取り込む
  4. a を stash 内で見つけ、read なら値を返す / write なら値を更新
  5. write_back(x):                 # 経路を根→葉の逆順で書き戻す
       各バケットに、stash 内のブロックのうち
       「新しい割り当てリーフへの経路がこのバケットを通る」ものを
       なるべく深い位置へ詰め、残りはダミーで埋めて再暗号化

肝は 2 行目 です。アクセスのたびに対象ブロック a の割り当てリーフを一様乱数で引き直すため、次に a を触るときの経路は前回と無相関になります。同じ番地を 100 回読んでも、サーバーが見る経路は毎回独立にランダムなリーフへの経路で、どれも区別がつきません。これがアクセスパターン秘匿の数学的な根拠です。

書き戻し（5 行目）では、各ブロックを「自分の新リーフへの経路と、いま書き戻している経路 x が共有する最も深いバケット」に押し込みます。根に近いバケットほど多くの経路が共有するため、押し込めなかったブロックは一時的にスタッシュへ残ります。Stefanov らはバケット容量 Z = 4 ならスタッシュ溢れ確率が log N に対して指数的に小さいことを証明しており、O(log N) サイズのスタッシュで実用上あふれません。

性能コストと PIR との関係

ORAM の代償は明確です。1 論理アクセスごとに log N 個のバケット（各 Z ブロック）を読み書きするため、帯域オーバーヘッドは概ね O(log N) 倍（定数込みで実測は数十倍に達することも多い）。さらにラウンドトリップが経路の深さ分だけ増え、レイテンシも悪化します。ポジションマップ自体が O(N) で大きい場合は、それを再帰的に別の小さな Path ORAM に格納する（recursive Path ORAM）ことでクライアント記憶を O(log N) まで圧縮できますが、その分アクセスが多段になりコストが乗ります。

ここで混同しやすいのが PIR（Private Information Retrieval） との違いです。両者とも「何を読んだかをサーバーに隠す」点は同じですが、前提とコスト構造が異なります。

ざっくり言えば、ORAM はクライアントの状態と帯域でアクセスを隠し、PIR はサーバーの計算（多くは準同型演算による全 DB 走査）でクエリを隠す、という重心の違いです。単一サーバー型の計算量 PIR は 準同型暗号と秘密計算（MPC） を土台にすることが多く、サーバー計算が O(N) 重い一方でラウンドが少ない。ORAM はサーバーは単純なストレージで済むがラウンドと帯域が嵩む。用途（自分のデータか共有 DB か、書き込みの要否、ボトルネックが帯域か計算か）で選び分けます。

まとめ

暗号化はデータの中身を守りますが、どこを読んだかという足跡＝アクセスパターンは無防備に残り、そこから検索語・鍵・データ構造が高確率で漏れます。これは サイドチャネル攻撃 の一種であり、TEE とセキュアエンクレーブ のようにメモリを暗号化しても塞げません。

ORAM はこの漏洩を正面から消す技術で、論理アクセスを「読み・再暗号化・別位置へ書き戻し」の物理列に変換し、論理アドレスと物理アクセスを統計的に独立にします。素朴な全走査の O(N) から、Square-Root ORAM の O(√N)、そして二分木とポジションマップ・スタッシュで O(log N) を実現する Path ORAM へと洗練され、その核心はアクセスのたびに対象ブロックの割り当てリーフを一様乱択し直すことにあります。Ω(log N) の下界がある以上、対数倍のコストは原理的に避けられません。クエリのインデックスを隠す PIR は、サーバー側 DB を私的に引くために重いサーバー計算を払う点で ORAM とは別物です。「見せずに使う」を別アプローチで追う技術として 準同型暗号と秘密計算（MPC）、統計公開での個人秘匿を担う 差分プライバシー と併せて押さえると、データを使いながら漏らさない技術群の見取り図が描けます。