Circuit ORAMと実用上のパフォーマンス

Wang、Chan、Shi（2015）によって提案されたCircuit ORAMは、帯域幅のオーバーヘッドを最小限に抑えながら、安全な計算フレームワーク（garbled circuitや秘密分散）で簡単に実装できるよう設計されました。主要な革新は、障害確率を無視できる水準に保ちながら、バケットサイズをZ = 2ブロックに削減したことです（Path ORAMではZ = 5）。これにより帯域幅が半分になります。追い出し手順も、小規模なブール回路として表現できるように再設計されました。

Z = 5のPath ORAMでは、ブロックをパスにランダムに割り当てた際に生じる可能性がある衝突に対応するため、各バケットに複数のブロックを格納することでstashのオーバーフロー確率を抑えています。Circuit ORAMは、ランダムな追い出しではなく決定論的な追い出し手順（深さ優先追い出し）を使用すれば、Z = 2で十分であることを証明しました。これにより、同じセキュリティパラメータで比較した場合、Path ORAMに対してサーバーストレージと通信のオーバーヘッドが半分になります。

Circuit ORAMは、効率的なブール回路として表現できる追い出し手順を備えることを目的に設計されました。安全な計算プロトコル（garbled circuit、SPDZ）では、ORAMアクセス自体をオブリビアスに評価する必要があります。つまり、計算を実行するサーバーに、どのメモリ位置がアクセスされたかを知られてはなりません。Circuit ORAMの単純な決定論的追い出し回路は、Path ORAMの追い出し手順よりもはるかに効率的にgarbled circuit化できます。

BバイトのブロックN個からなるデータベースの場合、Circuit ORAMではアクセス1回あたり2 * log N * Bバイトが必要です（バケットあたりZ = 2ブロックのパスを1本読み書きします）。4KBのブロックがN = 2^20個ある場合、アクセス1回あたり160KBとなり、Path ORAMの400KBと比べて少なくなります。一般的なパラメータでの平文に対する帯域幅オーバーヘッドは約40倍で、Path ORAMの100倍から削減されています。

Oblix（Misra、Schlegel、Sherwood、Tsudik、2018）はCircuit ORAMを使用して、高水準データ構造のオブリビアス版を構築します。これには、オブリビアス連結リスト、オブリビアスマップ（ハッシュテーブル）、オブリビアス優先度キューが含まれます。これらの構造により、アクセスパターンを明らかにせずに動的データをオブリビアスに計算できます。OblixはIntel SGXエンクレーブ内で動作し、安全なプライベート集合積計算やプライベートデータベースクエリを対象としています。

TaoStore（Sahin, Zhu, Gunter, Borisov, 2016）は、複数のORAMリクエストを並列に処理し、パスのエビクションをバッチ処理することで、高スループットの非同期アクセスをサポートするようPath ORAMを拡張します。同じパスへのアクセスをまとめることで、TaoStoreは同期型ORAM構成よりも大幅に高いスループット（1秒あたりのリクエスト数）を実現し、多数のクライアントが同時に接続するクラウドストレージサーバーに適したものとなっています。

Obladi（Crooks, Park, Alvisi, Iyengar, 2018）は、Path ORAM上に完全なトランザクションストレージシステムを構築します。Obladiは、暗号化され、アクセスパターンを秘匿するストレージ上でACIDトランザクションをサポートします。遅延実行を導入し、トランザクションをエポック単位でバッチ化して、各エポック内でどのレコードが具体的にアクセスされたかを隠す方法で実行します。Obladiは、クライアントと信頼できないクラウドストレージバックエンドの間で、信頼できるプロキシとして動作します。

1GBのORAM（4KBブロック262,144個）をAWS上に配置し、クライアントがインターネット経由でブロックにアクセスする場合、Path ORAMのレイテンシはアクセス1回あたり約50～200msです（log N = 18回のバケットアクセスにかかる往復時間が主な要因です）。バケットを並列に取得すれば、このレイテンシを短縮できます。ORAMをRAM上で実行するローカルSGXアプリケーションでは、レイテンシはアクセス1回あたり1～10msであり、多くのセキュア計算アプリケーションで許容できる範囲です。

ORAMの帯域幅オーバーヘッドは、アクセスパターンに大きく左右されます。1MBブロックを使用する1TBのクラウドストレージORAMでは、1回のアクセスで約25MBを転送します（log N = 25レベルによる25倍のオーバーヘッドです）。小さなブロック（4KB）では、アクセスごとのオーバーヘッドは絶対的なバイト数では小さくなりますが、相対的には大きくなります。ORAMを導入する組織は、帯域幅が20～50倍に増幅されることを見込み、ネットワークリンクとクラウドのエグレス料金にこの影響を織り込む必要があります。

アクセスプライバシーを実現するORAMの代替手段は、トラステッドハードウェアです。Intel SGXやAMD SEVは、適切な防御策を講じれば、ホストOSでさえ計算内容やメモリアクセスパターンを観測できないトラステッド実行環境を提供します。ただし、ORAMを使用しないSGXでは、ページレベルのアクセスパターンがハードウェアに漏洩するため、完全な保護にはSGX内のORAMが必要です。純粋なORAMと比較すると、トラステッドハードウェアは帯域幅オーバーヘッドを削減できますが、ハードウェアメーカーとサプライチェーンを信頼しなければなりません。

ORAMは、攻撃者がサーバー側のアクセスパターンを監視し（クラウドプロバイダーや同居テナントなど）、データの機密性から20～50倍の帯域幅オーバーヘッドを許容でき、アクセスパターン自体が機密情報を明らかにする場合に適しています。ほとんどのアプリケーションでは、慎重な鍵管理を伴う標準的な暗号化で十分です。ORAMは、医療データ分析、プライベート機械学習、金融取引システム、法執行機関のデータベースなど、高いセキュリティが求められる場面に特化したツールです。

Circuit ORAMはどのようなバケットサイズを使用しますか。また、それはPath ORAMよりどのように改善されているのでしょうか。

Circuit ORAMは、決定論的な深さ優先エビクションによって帯域幅を半減させるため、バケットサイズをZ=2に縮小しています（Path ORAMではZ=5です）。これは、ガーブルド回路によるセキュア計算の内部で使用することを想定して設計されています。代表的なパラメータでは、実用上のオーバーヘッドは帯域幅の40倍の増幅です。実運用システムには、Oblix（SGXと秘匿データ構造）、TaoStore（高スループットのバッチ処理ORAM）、Obladi（トランザクション型ORAM）があります。SGX単体ではページレベルのアクセスパターンが漏洩するため、SGX内のORAMが必要です。