プライベート問合せにおける問合せ頻度を用いた制約緩和手法 Frequency-based Constraint Relaxation for Private Query

この論文にアクセスする

この論文をさがす

抄録

本論文では,プライベート問合せにおける問合せの頻度を用いた制約緩和手法を提案する.プライベート問合せとは,データベースの利用者が何を問い合わせているのか,すなわち検索意図を隠したまま目的のアイテムを取得する問合せ手法である.既存手法の多くは,i) サーバは実際の値を知ることはできないが問合せ処理のみ実行できる形式に問合せおよび問合せ結果を符号化する,ii) サーバは問合せ処理時にすべてのアイテムを走査する,という2条件を用いてプライベート問合せを実現している.その結果,サーバが攻撃者となる場合であっても,どのアイテムが実際に問い合わせられたのかを隠すことができる.しかし,この2つ目の条件によりサーバにおける問合せ処理コストはサーバが保持するアイテムの総数を n として O(n) となる.本論文で提案する制約緩和手法は,この2つ目の条件を緩和し多くの場合でデータベースの一部分の走査でプライベート問合せを実現する.提案手法は,一次元データベースに対する一致問合せだけでなく,範囲問合せや二次元データベースに対する一致問合せにも利用できる.We introduce a frequency-based constraint relaxation methodology for private queries. Private queries undergo processing in order to allow people to obtain data from a database without exposing which data the user is interested in (search intention). Most existing protocols for private querying achieve this by the following two constraints: i) queries and query results are encoded so that the database server cannot actually decode queries but can handle query processes; ii) the server is forced to check all data in the server when computing query results. Because of these constraints, even database servers cannot distinguish which data are selected from the database. However, this second constraint compels servers to spend O(n) computational cost for each query processed, where n is the number of data entries on the server. Our relaxation methodology relaxes this constraint and allows private querying while only examining a portion of the data in most cases. Our methodology is also flexible and applies not only to exact match queries in one dimensional data but also to range queries in one dimensional data and exact match queries in two dimensional data.

収録刊行物

  • 情報処理学会論文誌データベース(TOD)

    情報処理学会論文誌データベース(TOD) 6(3), 50-60, 2013-06-28

    情報処理学会

各種コード

  • NII論文ID(NAID)
    110009579665
  • NII書誌ID(NCID)
    AA11464847
  • 本文言語コード
    JPN
  • 資料種別
    Article
  • ISSN
    1882-7799
  • データ提供元
    NII-ELS  IR  IPSJ 
ページトップへ