プライベート問合せにおける問合せ頻度を用いた制約緩和手法

概要

論文の詳細を見る
本論文では,プライベート問合せにおける問合せの頻度を用いた制約緩和手法を提案する.プライベート問合せとは,データベースの利用者が何を問い合わせているのか,すなわち検索意図を隠したまま目的のアイテムを取得する問合せ手法である.既存手法の多くは,i) サーバは実際の値を知ることはできないが問合せ処理のみ実行できる形式に問合せおよび問合せ結果を符号化する,ii) サーバは問合せ処理時にすべてのアイテムを走査する,という2条件を用いてプライベート問合せを実現している.その結果,サーバが攻撃者となる場合であっても,どのアイテムが実際に問い合わせられたのかを隠すことができる.しかし,この2つ目の条件によりサーバにおける問合せ処理コストはサーバが保持するアイテムの総数を n として O(n) となる.本論文で提案する制約緩和手法は,この2つ目の条件を緩和し多くの場合でデータベースの一部分の走査でプライベート問合せを実現する.提案手法は,一次元データベースに対する一致問合せだけでなく,範囲問合せや二次元データベースに対する一致問合せにも利用できる.
2013-06-28