2023年度 ISS Squareシンポジウム (2024/3/1)

No.211

オンラインデータの安全な利用に向けた共通鍵検索可能暗号の研究
Searchable Symmetric Encryption for Secure Utilization of Online Data
佐藤敬恒・法制倫理分科会・情報セキュリティ大学院大学
Abstract: With the spread of the online preservation, Searchable Symmetric Encryption (SSE), which realizes searching of encrypted documents
through encrypted queries, has been paid attention. A lot of SSE scheme allow the leakage of access patterns and search patterns. However,recent works show that adversaries having some auxiliary information can exploit those information leakage, and perform query recovery attacks toguess keywords corresponding to encrypted search queries. Although an SSE framework proposed by Chen et al. (IEEE INFOCOM 2018) prevents
access pattern leakage with use of erasure coding to make documents redundant into multiple shards and perturbing the registration of theseshards to encrypted indexes, this framework doesn’t provide the protection for query recovery attack based on search pattern leakage. We propose
an SSE scheme to create several small indexes, which contains identifiers of document's shards obtained by Erasure Coding. Our scheme offerscountermeasure of query recovery attacks based on access pattern leakage or search pattern leakage.

1.検索可能暗号とは

5.提案方式の工夫【索引1】

olympics rugby●Erasure Codingを使用して生成した
࢏ࢊ૚૚
࢏ࢊ૚૚
破片文書のうち、決まった種類のもの
࢏ࢊ૚૛
࢏ࢊ૚૛
を用いた索引を複数件用意する。
࢏ࢊ૚૜ …
࢏ࢊ૚૜●索引で登録対象となる破片文書のうち、 ࢏ࢊ૛૚࢏ࢊ૛૚࢏ࢊ૛૜キーワードとの対応関係があるものは、 ࢏ࢊ૛૛全て関連付けをする。また索引で登録 【索引2】
対象となる破片文書のうち、キーワー
olympics rugby
ドとの対応関係がないものも、ダミー࢏ࢊ૚૚࢏ࢊ૚૚
としてランダムに関連付ける。
࢏ࢊ૚૜࢏ࢊ૚૜
暗号化状態で検索を実現する検索可能暗号が注目される。
࢏ࢊ૚૝࢏ࢊ૚૝ …
●検索ではキーワードとともに、任意の࢏ࢊ૛૜࢏ࢊ૛૚
索引番号を選択する。対応関係にある
࢏ࢊ૛૝࢏ࢊ૛૝
2.クエリ回復攻撃とは破片文書と、ダミーの破片文書の取得
平文キーワード推測
割合も考慮のうえで検索する。
【文書本体】●暗号化文書の保存や検索のサーバ（例） 破片文書を3種類ずつ用いて、2つの文書処理過程で、サーバ(攻撃(攻撃者)࢏ࢊ૚૚ ࢏ࢊ૚૜ ࢏ࢊ૛૚ ࢏ࢊ૛૜索引を用意する。検索においては、暗号化…
者)は検索時期や検索結果の対応関係にある一定数以上の破片文
࢏ࢊ૚૛ ࢏ࢊ૚૝ ࢏ࢊ૛૛ ࢏ࢊ૛૝応答件数を観測できる。
書をのように取得する。ダミー
検索文書の検索も行い撹乱する。
●サーバが平文文書の一部や●クラウド活用が推進される中、オンライン上にデータを保存する需要も拡大しつつある。
●データを暗号化しなければ、サーバ管理者の不正な閲覧やデータ流出による情報漏洩が心配である。
●通常の暗号化では、大量のデータの中から必要なデータを検索することができないため不便である。

検索頻度の情報を知っていると、クエリに対応する平文キーワードを推測しうる。
(クエリ回復攻撃)

6.提案方式と検索頻度の分散
補助情報 ・ 一部の平文文書
・ 検索頻度の情報

3.既存の対策方式 [1]【索引】
olympics rugby●データ保護技術であるErasure Coding࢏ࢊ૚૚࢏ࢊ૚૚を使用して，登録文書を冗長化する。
࢏ࢊ૚૛࢏ࢊ૚૛࢏ࢊ૚૜
●冗長化した文書(破片文書)の一部を࢏ࢊ૚૜࢏ࢊ૚૝
キーワードと関連づけて索引登録する。 ࢏ࢊ૚૝࢏ࢊ૛૚࢏ࢊ૛૛

●キーワードと無関係な破片文書もダミーとして索引へ登録する。

…

【文書本体】（例） olympicsとrugbyとも݅݀ଵ の文書と対応࢏ࢊ૚૚ ࢏ࢊ૚૜ ࢏ࢊ૛૚ ࢏ࢊ૛૜…
しているとする。対策を適用すると
࢏ࢊ૚ の文書は࢏ࢊ૚૚ ~࢏ࢊ૚૝ に冗長化され、 ࢏ࢊ૚૛ ࢏ࢊ૚૝ ࢏ࢊ૛૛ ࢏ࢊ૛૝撹乱された索引が構成される。これによりクエリ回復攻撃を困難にする。 ※破片文書2つで文書を復元できるとする

4.検索頻度の情報を用いた攻撃●[1]の対策方式では、キーワードの検索時期は撹乱されず、攻撃者は検索頻度を用いたクエリ回復攻撃を実行しうる。
（例）クエリ‫ ݍ‬はolympicsとrugbyのいずれଵ

かのキーワードと対応しているとする。ࢗ૚ は2021年に多く発行されたとすれば、世間の注目状況からࢗ૚ はolympicsに対応すると推測できる。

図 世間の注目状況(イメージとして作成)●提案方式では攻撃者はユーザの選択した索引番号を困難にする。これにより複数の索引に検索先を適切に分散させることで、観測されるクエリの発行頻度を撹乱する。
●分散方法として、索引ごとに選択確率を重み付け確率を設定した上、検索回数や時期に応じて不定期に設定値を更新するなどが考えられる。

図 検索頻度の分散(イメージとして作成)

7.提案方式に対する評価結果●Google Trends[2]と同じ検索頻度で、ユーザがキーワードの暗号化検索を行い、攻撃者が全クエリのうち正確に予測できた割合を評価した。
●Enronデータセット[3]の上位250件のキーワードを検索対象とする。
●攻撃者は検索キーワードの種類とGoogle Trends上の検索頻度を知っている前提とする。
攻撃者の正解率は低下し、有効性を確認できた。
[1] G. Chen, T. Lai, M. K. Reiter, and Y. Zhang. Differentiallyprivate access patterns for searchable symmetric encryption.
In IEEE INFOCOM 2018, pp.810-818, 2018.
[2] Google, 2024, “Google Trends”, (https://trends.google.co.jp/trends/, 2024-02-07 参照)[3] William W. Cohen, 2015, “Enron email dataset”, (https://www.
cs.cmu.edu/~./enron/, 2024-02-07参照)