クラウドストレージとセキュアプロセッサにおけるORAM

Intel SGX（Software Guard Extensions）は、コードとデータが暗号化および認証される、ハードウェアで隔離されたエンクレーブを提供します。しかし、オペレーティングシステムは、ページテーブルエントリを監視することで、エンクレーブがどのメモリページにアクセスしたかを観測できます。このページレベルのアクセスパターンは、サイドチャネル攻撃に悪用される可能性があります。代表的な攻撃がXu、Cui、Peinado（2015）による「controlled channel attack」であり、SGXのメモリアクセスパターンからRSA鍵を復元しました。

SGXは、ページレベルのアクセスパターンだけでなく、キャッシュタイミングサイドチャネルにも脆弱です。プロセッサを共有する攻撃者は、エンクレーブによって発生するキャッシュヒットとキャッシュミスを観測し、より細粒度のアクセスパターン（キャッシュラインレベル）を推測できます。これらの攻撃が可能なのは、CPUキャッシュがエンクレーブと信頼できないコードの間で共有されているためです。対策には、定数時間プログラミングや、メモリアクセスパターンをランダム化するORAMなどがあります。

ZeroTrace（Sasy, Jha, Kerschbaum, 2018）は、Intel SGXエンクレーブ内にPath ORAMを実装し、秘匿メモリアクセスを提供します。信頼できないホストOSがORAMサーバー（バケットの二分木）を提供し、SGXエンクレーブがORAMクライアントとして動作します。ZeroTraceはSGX固有の最適化として、位置マップをエンクレーブ内の信頼できるメモリに保持し、位置マップに対する再帰的ORAMを不要にします。

Graphene-SGX（現在のGramine）とSCONEは、変更されていないLinuxアプリケーションをエンクレーブ内で実行できるSGXコンテナフレームワークです。どちらのフレームワークも、OSからアクセスパターンを隠すためのORAMサポートが追加されています。ORAMを統合したSCONEでは、コードを変更せずにSGX内でPython、Go、Javaプログラムを秘匿実行できるため、手動で統合しなくてもアプリケーションでORAMを利用できます。

Shroud（Volos, Jaleel, Emer, Burtscher, Forlin, 2018）は、SGXエンクレーブ内で使用する基本データ構造（配列、スタック、キュー、マップ）の秘匿版を実装します。Shroudは、ORAMとデータ非依存アルゴリズムを組み合わせ、エンクレーブのメモリアクセスパターンがデータ値に依存しないようにします。アプリケーションメモリ全体にORAMを適用するよりも効率的であり、機密性の高いデータ構造だけを対象にします。

AWS Nitro Enclavesは、決済カード番号や医療記録など、非常に機密性の高いデータを処理するための隔離されたコンピューティング環境を提供します。SGXとは異なり、Nitro Enclavesはプロセスレベルではなく仮想マシンレベルで隔離します。AWSはNitro EnclavesでデフォルトのORAMを提供していませんが、機密性の保証によってメモリ内容は保護されます。アクセスパターンの秘匿が必要な場合、Nitro Enclaves上で動作するアプリケーションが独自にORAMを実装する必要があります。

ARM TrustZoneは、通常のOSから隔離されたトラステッド実行環境（Secure World）を提供します。SGXと同様に、TrustZoneはメモリアクセスパターンを本質的に隠すわけではありません。TrustORAM（Brasser, Dmitrienko, Sadeghi, Crane, Larsen, Franz）などの研究システムは、TrustZone内にORAMを実装し、モバイルデバイスやIoTにおける機密データへのアクセスを保護します。TrustZoneは現在のすべてのARMプロセッサに搭載されているため、ORAM対応のTrustZoneを幅広く導入できます。

ObliDB（Eskandarian and Boneh, 2017）は、標準的なSQLクエリのアクセスパターンを隠す秘匿データベースです。点クエリにはORAMを、範囲クエリには秘匿ソートを使用します。Opaque（Zheng, Dave, Beekman, Popa, Hellerstein, Stoica, 2017）は、Intel SGXとORAMを使用し、Apache Spark上でSQLクエリを秘匿的に実行します。Opaqueは、ORAMのオーバーヘッドがあっても、本番規模のデータ分析（数百万件のレコード）が実現可能であることを示しています。

プライベート情報検索（PIR）は、読み取り専用のアクセスパターン秘匿を実現する関連プリミティブです。PIRを使用すると、サーバーにどの要素を取得したかを知られることなく、クライアントがデータベースの要素を取得できます。計算量的PIR（cPIR）は、サーバーストレージのオーバーヘッドO(1)と、通信量O(sqrt(n))またはO(polylog n)を実現します。PIRは読み取り専用ワークロードではORAMより効率的ですが、秘匿書き込みには対応できません。

読み取り専用アクセスでは、PIRのほうがORAMより通信効率に優れています。単一サーバーのcPIRでは通信量がO(n^epsilon)であるのに対し、ORAMではアクセスごとにO(log n)個のブロックが必要です。ただし、PIRではサーバー側の計算（単一サーバーPIRではデータベースサイズに対して線形）が必要なのに対し、ORAMではすべての計算をクライアント側で行います。マルチサーバーPIRは、2台の非共謀サーバーを用いることで情報理論的安全性を実現し、非常に効率的で、CDNへの導入に適しています。

ORAMの研究方向には、通信オーバーヘッドを理論上のO(log n)の下限に近づけること（OptORAMaは漸近的にこれを達成します）、量子RAM（QRAM）向けのORAM、差分プライベートORAM（同じブロックが2回アクセスされたかどうかを隠すもの）、準同型暗号におけるORAM（外部委託計算向けのFHE-ORAM）などがあります。ORAMとハードウェアベースのトラステッド実行環境の統合は、実用面で最も大きな効果が期待される研究方向です。

Intel SGXではページレベルおよびキャッシュレベルのアクセスパターンが漏洩するため、controlled-channel攻撃やキャッシュタイミング攻撃が可能になります。ZeroTraceはSGX内にPath ORAMを実装し、これらの漏洩を排除します。Graphene-SGXとSCONEは、コンテナレベルでのORAM統合を提供します。ObliDBとOpaqueは、本番規模でORAM上の秘匿SQLが実現可能であることを示しています。PIRは読み取り専用アクセスに対する効率的な代替手段です。ORAMの研究は、log nの通信量下限と準同型暗号との統合に向けて、現在も進められています。