プライバシーを考慮した効果的な情報獲得

概要

論文の詳細を見る
プライバシーを考慮したk(⩾1)個のデータベースからの情報獲得(Private Information Retrieval with k databases: k-PIR)とは, 以下のような手法のことを言う:(1)ユーザが互いに通信を行なわないk個の同一データベースにアクセスし;(2)ユーザがデータベースに"どのデータを獲得したか"を一切漏らすことなく必要なデータを獲得する.このような手法においてその効率を評価する際に, ユーザとデータベース間の通信量と時間計算量が重要な意味を持つ.これまでに, Chorらは被覆符合の概念を導入することにより, 通信量12n^<1/3>+2の2-PIRを提案している(ただしnはデータベースに保存されている全データのビット長を表すものとする).一方, AmbainisはChorらの方法を再帰的に拡張し, 全てのk⩾2に対して, 高々通信量c_k・n^<1/(2k-1)>のk-PIRを提案している.本研究では, 被覆符合の条件を緩和することにより, Chorらの方法に比べ時間計算量の少ない通信量12n^<1/3>の2-PIRを提案する.また本論文では, Ambainisの再帰的構成法を一般的に定式化し, その最適化を行うことによって, 全てのk⩾4に対して, 高々通信量c^l_k・n^<1/(2k-1)>のk-PIR(ただしc^l_k≪c_k)を提案する.
1998-05-15