Path ORAM：メモリアクセスの秘匿

Stefanov、van Dijk、Shi、Fletcher、Ren、Yu、Devadas（2013）によって提案されたPath ORAMは、実用面で最も影響力のあるORAM構成です。サーバーストレージをバケットの二分木として構成し、各リーフをデータブロックの配置先に対応させます。Path ORAMは基本形でアクセス1回あたりO(log^2 N)の通信オーバーヘッドを実現し、数百行のコードで実装できるほど構造が単純です。

ポジションマップは、各論理ブロックアドレスを二分木のリーフノードに対応付けるクライアント側のデータ構造です。N個のブロックがあり、木の高さがL = log Nであるデータベースでは、ポジションマップはN個のリーフインデックスからなる配列です。ブロックbにアクセスする前に、クライアントはポジションマップで現在割り当てられているリーフを検索し、新しいランダムなリーフを割り当てます。古いリーフのパスがサーバーから読み取られ、サーバーに書き戻されます。

stashは、サーバーから読み取られたものの、まだ書き戻されていないブロックを一時的に保持する、クライアント側の小さなバッファ（通常は20～40ブロック）です。ブロックを読み取ると、そのブロックはパスから取り出されてstashに置かれます。アクセスや変更が行われた後、新しいパスに配置できるstash内のすべてのブロックが書き戻されます。パスに収まらないブロックはstashに残ります。

サーバーストレージはL+1レベルの完全二分木です（L = log N）。各ノード（バケット）はZ個のブロックを保持します（通常はZ = 5）。リーフはデータブロックの配置先に対応します。リーフノードはN個あるため、ノードの総数は2N-1、サーバーストレージの総量はO(NZ)です。各リーフからルートまでのパスにはlog N個のノードがあり、Z*log N個のブロックを保持できるため、パス追い出し戦略に必要な容量を確保できます。

ブロックbを読み取る手順は次のとおりです。(1) ポジションマップでbの現在のリーフlを検索する。(2) bに新しいランダムなリーフl'を割り当て、ポジションマップを更新する。(3) リーフlからルートまでのパスにあるすべてのバケットを読み取る（log N個のバケット）。(4) 読み取ったパスまたはstashからブロックbを探す。(5) 新しいパスl'に割り当てられるすべてのブロックを書き戻し、残りのバケットスロットをダミーブロックで埋める。サーバーからは、毎回ランダムなパスが読み取られるように見えます。

Path ORAMがオブリビアス性を維持できるのは、どのブロックにアクセスするかに関係なく、アクセスごとに必ずルートからリーフまでの1本のパスを読み書きするためです。パスはブロックの内容やアドレスではなく、一様にランダムなリーフ割り当てによって決まります。空いているバケットスロットはダミーブロックで埋められるため、すべてのパスで占有スロット数が同じになります。サーバーを監視する攻撃者に見えるのは、ランダムなパスへのアクセスだけです。

Path ORAMのアクセス1回では、ルートからリーフまでの1本のパスを読み書きします。つまり、Z個のブロックからなるバケットをO(log N)個処理します。ブロックサイズをB、バケットサイズをZとすると、アクセス1回で転送されるデータ量はO(Z * log N * B)ビットです。一般的なパラメータ（N = 2^20、Z = 5、B = 4KB）では、これはアクセス1回あたり約400KBであり、平文アクセスの4KBと比べて100倍のオーバーヘッドになります。再帰的ポジションマップにより、ブロック数を基準にした通信量をO(log^2 N)まで削減できます。

単純なポジションマップでは、クライアントにN個のエントリを格納する必要があり、クライアントストレージはO(N)となります。これはデータベース全体と同じ規模です。再帰的ポジションマップでは、ポジションマップ自体をより小さなORAMに再帰的に格納することで、クライアントストレージをO(log^2 N)まで縮小します。ORAMがstashに収まるほど小さくなった時点で再帰は終了します。これは、大規模なデータセットでPath ORAMを実用化するための標準的な手法です。

Path ORAMでは、ブロックを割り当てられたパスに追い出せないパス競合が発生すると、stashのサイズが増加します。Stefanovらは、stashがオーバーフローする（Rブロックを超える）確率はRに対して指数関数的に小さくなること、具体的には標準的な分析で最大でも14 * (0.6002)^Rであることを証明しました。R = 40に設定すると、障害確率は約2^{-38}になります。この結果は、攻撃者が選んだアクセスシーケンスを含むすべてのアクセスシーケンスに対して成り立ちます。

Path ORAM以前は、実用的なORAM構成で最も優れていたものでもオーバーヘッドはO(log^3 N)でした（Shiら、2011年、"Oblivious RAM with O((log N)^3) Worst-Case Cost"）。Path ORAMは、より単純な構造でこれをO(log^2 N)まで削減しました。その後の研究（Circuit ORAM、OptORAMa）では定数や漸近的な上限がさらに改善されましたが、Path ORAMは単純であるため、現在も最も広く実装されている構成です。

Path ORAMは、数十の研究用および実運用システムに実装されています。ZeroTrace（Intel SGX + Path ORAM）、Obladi（クラウドストレージ上のPath ORAM）、Opaque（Apache Spark上のPath ORAM）などが代表的な実装です。Stanfordの安全な計算グループは、オープンソースのC++ Path ORAM実装を保守しています。AWSは、プライバシーを保護したデータ分析の研究プロトタイプであるNitro Enclavesの一部としてPath ORAMを提供しています。

Path ORAMにおけるポジションマップの役割は何ですか。

Path ORAMはサーバーストレージを二分木として構成し、アクセスごとにルートからリーフまでの1本のパスを読み書きします。ポジションマップは各ブロックの現在のリーフ割り当てを追跡し、stashは最近アクセスされたブロックを一時的に保持します。アクセスごとに新しいランダムなリーフ位置を割り当てることでアクセスをすべてランダム化し、サーバーから見えるすべてのアクセスを同じ分布にします。アクセス1回あたりの通信オーバーヘッドはO(Z * log N)です。再帰的ポジションマップにより、クライアントストレージはO(log^2 N)まで削減されます。Path ORAMは最も広く実装されているORAM構成です。