@inproceedings{oai:ipsj.ixsq.nii.ac.jp:00214491,
 author = {小谷, 俊輔 and 國廣, 昇 and Shunsuke, Odani and Noboru, Kunihiro},
 book = {コンピュータセキュリティシンポジウム2021論文集},
 month = {Oct},
 note = {暗号化データベースに対するレンジクエリの応答ボリュームサイズを観測することにより， データベース全体のヒストグラムを復元する攻撃が提案されている．この攻撃では，固定の窓幅 b に対して，幅 b 以下の全てのクエリ対する応答ボリュームサイズが得られるという仮定のもとで復元を行う．ボリュームサイズに偏りが大きい状況で，ボリュームサイズにノイズが全く無いときには，容易にデータベース全体のヒストグラムを復元することが可能である．一方，ノイズが存在する状況は，既存研究では考慮されておらず，どの程度のノイズが乗っても復元できるかは明らかではない．本発表では，b が 2 であり，ボリュームサイズに偏りが大きいという仮定のもとで，ノイズがある場合にも有効な攻撃を提案する．提案手法では，観測したボリュームサイズをもとに，グラフ理論的なアプローチにより，ヒストグラムの復元を行う．観測したボリュームサイズからグラフを構成し，頂点を少なくとも一度通る経路を探索することにより，データ全体を復元している．さらに，人工的なデータを用いて実験を行い，ボリュームサイズの偏りやノイズをパラメータとしたデータベース復元率の評価を行う．, 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.},
 pages = {676--683},
 publisher = {情報処理学会},
 title = {レンジクエリに対するノイズ付きボリューム漏洩攻撃},
 year = {2021}
}