プライバシーを考慮した情報獲得プロトコルの通信量の下界

概要

論文の詳細を見る
プライバシーを考慮したκ≥1個のデータベースからの情報獲得(Private) Information Retrieval with κ databases:(κ, l)-PIR)とは-(1)ユーザが互いに通信を行なわないκ個の同一データベースに対してl項組の質問を送信する;(2)各データベースはそれに対応する答えをユーザに送信する;(3)ユーザがデータベースに"どのデータを獲得したか"を一切漏らすことなく必要なデータを獲得する-ようなプロトコルのことを言う.このようなプロトコルにおいてその効率を評価する際に, ユーザとデータベース間の通信量が重要な意味を持つが, その下界については(極めて特殊な場合を除き)全く未解明である.そこで本論文では, ユーザのデータベースに対する質問とそれに対応するデータベースの答えの間の関係に注目し, (κ, l)-PIRを線形型・多重線形型・アフィン型に分類する.そして, それぞれの型に関して, (κ, l)-PIRの通信量の下界-(1)多重線形型(κ, l)-PIRの通信量の下界はΩ(^l+1√<n>)である(Theorem3.1);(2線形型)κ-PIRの通信量の下界はΩ(√<n>)である(Corollary3.2);(3)アフィン型(κ, l)-PIRの通信量の下界はΩ(^l+1√<n>)である(Theorem4.2)-を示す.
社団法人電子情報通信学会の論文
2000-05-11