アクセスパターン漏洩の脅威

データを暗号化すると、権限のない第三者からその内容を保護できますが、暗号化だけではデータへのアクセス方法に関するメタデータを隠せません。アクセスパターン、つまりどのレコードが読み書きされたか、いつ、どのくらいの頻度でアクセスされたかは、データ自体が完全に暗号化されていても、機密情報を明らかにする可能性があります。この内容のプライバシーとアクセスのプライバシーの隔たりが、Oblivious RAMの中核的な動機です。

アクセスパターンの分析からは、次のような情報が明らかになる可能性があります。ユーザーがどのデータベースレコードをクエリするか（アクセスしたレコードから病気を推測できます）、通信パターン（メッセージの内容が暗号化されていても、誰が誰に連絡しているかが分かります）、金銭的な活動（ユーザーがどの価格情報を要求するかから取引戦略を推測できます）、行動パターン（アクセス時刻と頻度から日々の生活パターンを推測できます）。このような推測は、データの内容そのものと同じ程度に機密性の高いものとなる可能性があります。

CryptDB（MIT、2011年）は、暗号化データベースに対してクエリを実行する影響力の大きいシステムでした。その後のGrubbs、McPherson、Naveed、Ristenpart、Spoonerによる研究（2016年）では、CryptDBや類似する順序保存暗号方式が、推測攻撃を可能にするアクセスパターンを漏えいさせることが示されました。アクセス分布に関する補助データセットを持つ攻撃者は、暗号を破らなくても、アクセス頻度と順序だけから平文の値を推測できます。

暗号化されたクラウドストレージサービスが、どの暗号文ブロックにアクセスされたかを記録している場合、攻撃者は頻度分析を実行できます。ユーザーは人気のあるファイルにより頻繁にアクセスする傾向があるため、暗号文ブロックのアクセス頻度ヒストグラムは平文のアクセス分布を反映します。暗号化された頻度ヒストグラムを既知のアクセスパターンと照合することで、どの暗号化ファイルが人気のコンテンツカテゴリに対応するかを特定できます。

正直だが好奇心旺盛（半正直）な脅威モデルでは、クラウドプロバイダーはプロトコルに従って正しく動作しますが、クライアントデータへのすべてのアクセスパターンを監視します。多くのクラウドプロバイダーは、課金、デバッグ、パフォーマンス最適化のためにアクセスパターンを正当に記録しています。悪意がなくても、こうしたログはリスクを生みます。クラウドプロバイダーが侵害された場合や、悪意のある従業員、政府による召喚状によって、機密性の高いアクセスパターンが明らかになる可能性があります。

Goldreich と Ostrovsky（1996）が提案した Oblivious RAM（ORAM）は、サーバーからアクセスパターンを隠す暗号プリミティブです。ORAM方式では、実際にアクセスしている場所がどこであるかに関係なく、任意のメモリ位置への各アクセス（読み取りまたは書き込み）が、サーバーから見える操作について同じ分布を生成します。サーバーを監視する攻撃者に見えるのは、一様にランダムなアクセスパターンだけです。

ORAMには、アクセスパターンのプライバシーが必要なさまざまな場面で幅広い応用があります。たとえば、安全なクラウドストレージ（ユーザーがどのファイルにアクセスするかを隠す）、秘匿データベースクエリ（クエリによってどの行が返されたかを隠す）、SGXエンクレーブ（エンクレーブメモリへのアクセスパターンをサイドチャネルから保護する）、Private Information Retrieval（ユーザーがどのデータベースエントリを取得するかを隠す）、安全なマルチパーティ計算（中間状態へのアクセスパターンを隠す）などです。

最も単純なORAMの解決策は、明らかに単純です。任意の1ブロックにアクセスする際、ストレージ全体のすべてのブロックを読み取り、書き戻します。これにより、どのブロックにアクセスしたかは隠されます（すべてのアクセスが同じに見えます）が、論理アクセス1回あたりO(n)の通信オーバーヘッドが発生するため、大規模なデータセットでは完全に実用的ではありません。実際のORAM方式では、完全オブリビアス性または統計的オブリビアス性を維持しながら、このオーバーヘッドをO(polylog n)まで削減することを目指します。

Goldreich と Ostrovsky は、次の下限を証明しました。サーバーストレージのオーバーヘッドがO(1)であるORAMは、アクセス1回あたり少なくともOmega(log n)の通信オーバーヘッドを負わなければなりません。この対数の下限は、決定論的ORAMに適用されます。実用的な構成では、理論上の最小値に近いO(log^2 n)またはO(log n)のオーバーヘッドの達成を目指します。この下限は、アクセスパターンを完全に隠すには避けられないコストが伴うことを示しています。

検索可能対称暗号（SSE）を使うと、暗号化されたデータを検索できます。基本的なSSE方式では、検索パターン（どのキーワードが検索されたか）とアクセスパターン（どのドキュメントが返されたか）が明らかになります。Forward-private SSEは新しいドキュメントに対する検索パターンを隠しますが、どのドキュメントにアクセスされたかまで隠すにはORAMが必要です。SSEとORAMを組み合わせると最も強力なプライバシー保証が得られますが、大きなパフォーマンスコストがかかります。

ORAMが常に必要とは限りません。判断は脅威モデルによって異なります。攻撃者はアクセスパターンを監視できるでしょうか。完全ディスク暗号化を使用したローカルストレージで、攻撃者がリモートにいる場合は、ORAMは必要ない可能性があります。クラウドプロバイダーを信頼できないクラウドストレージでは、ORAMが適しています。アクセスパターンの漏えいが現実的な脅威であり、データの機密性がコストを正当化する場合は、オーバーヘッド（通常は帯域幅の20～50倍）を受け入れる価値があります。

暗号化されたデータであってもアクセスパターンが機密情報となる理由を、正しく説明しているものは次のうちどれですか。

データの内容を暗号化してもアクセスパターンは隠れないため、頻度分析やタイミング分析によって機密情報が明らかになる可能性があります。正直だが好奇心旺盛なモデルのクラウドプロバイダーは、クライアントがどの暗号文ブロックにアクセスしたかを監視します。CryptDBへの攻撃によって、暗号化データベースのアクセスパターンから実際に情報を推測できることが示されました。ORAMは、すべてのアクセスをサーバーから同じに見えるようにすることで、この問題を解決します。単純な解決策（アクセスごとにすべてを読み取る方法）はO(n)で実用的ではありませんが、実際のORAMではO(log^2 n)のオーバーヘッドを実現します。