レンジクエリに対するノイズ付きボリューム漏洩攻撃

• Item type: Symposium(1)
• 公開日: 2021-10-19
• タイトル: レンジクエリに対するノイズ付きボリューム漏洩攻撃
• タイトル / 言語: en
• タイトル: Noisy Volume Leakage Attack against Range Queries
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: ボリューム漏洩攻撃，レンジクエリ，ノイズ
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 筑波大学情報理工学位プログラム
• 著者所属: 筑波大学システム情報系
• 著者所属(英): en
• 著者所属(英): Degree Programs in Systems and Information Engineering, University of Tsukuba
• 著者所属(英): en
• 著者所属(英): University of Tsukuba
• 著者名: 小谷, 俊輔; 國廣, 昇
• 著者名(英): Shunsuke, Odani; Noboru, Kunihiro
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 暗号化データベースに対するレンジクエリの応答ボリュームサイズを観測することにより， データベース全体のヒストグラムを復元する攻撃が提案されている．この攻撃では，固定の窓幅 b に対して，幅 b 以下の全てのクエリ対する応答ボリュームサイズが得られるという仮定のもとで復元を行う．ボリュームサイズに偏りが大きい状況で，ボリュームサイズにノイズが全く無いときには，容易にデータベース全体のヒストグラムを復元することが可能である．一方，ノイズが存在する状況は，既存研究では考慮されておらず，どの程度のノイズが乗っても復元できるかは明らかではない．本発表では，b が 2 であり，ボリュームサイズに偏りが大きいという仮定のもとで，ノイズがある場合にも有効な攻撃を提案する．提案手法では，観測したボリュームサイズをもとに，グラフ理論的なアプローチにより，ヒストグラムの復元を行う．観測したボリュームサイズからグラフを構成し，頂点を少なくとも一度通る経路を探索することにより，データ全体を復元している．さらに，人工的なデータを用いて実験を行い，ボリュームサイズの偏りやノイズをパラメータとしたデータベース復元率の評価を行う．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Many attacks have been proposed to recover the histogram of the encrypted database by using the observed response volume size of range queries. While it is easy to recover the histogram under the situation that the volume size is highly biased and includes no noise, the situation with noise has never been considered in existing works. It is not clear how much noise we can deal with. This paper proposes an effective attack under the assumption that there exists noise in the observed volume size for all queries of width one or two. In the proposed method, we employ a graph-theoretic approach. We construct a graph from the observed volume size and recover the histogram by finding paths passing through the vertices at least once. We also conduct experiments to evaluate the recovery rate from artificial data and show that our proposed algorithm is effective even if there exists noise.
• 書誌情報: コンピュータセキュリティシンポジウム2021論文集; p. 676-683, 発行日 2021-10-19
• 出版者 / 言語: ja
• 出版者: 情報処理学会