| 講演名 | 1998/5/15 プライバシーを考慮した効果的な情報獲得 伊東 利哉, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | プライバシーを考慮した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)を提案する. |
| 抄録(英) | Private information retrieval for k⩾1 databases (k-PIR) is a scheme that enables a user to make access to (separated) k replicated copies of a database and privately retrieve any single bit out of the n bits of data stored in the database. In this model, "privacy"implies that the user retrieves the bit he is interested in but releases to each database nothing about which bit he really tries to get. Chor et. al. proposed 2-PIR with communication complexity 12n^<1/3>+2 that is based on the covering codes. Then Ambainis recursively extended the scheme by Chor et. al. and showed that for each k⩾2, there exists k-PIR with communication complexity at most c_k・n^<1/(2k-1)> some constant c_k⩾0. In this paper, we relax the condition for the covering codes and present time-efficient 2-PIR with communication complexity 12n^<1/3>. In addition, we generally formulate the recursive scheme by Ambainis and show that for each k⩾4, there exists k-PIR with communication complexity at most c^l_k・n^<1/(2k-1)> for some constant c^l_k≪c_k. |
| キーワード(和) | 情報獲得 / 通信量 / 時間計算量 |
| キーワード(英) | Information Retrieval / Communication Complexity / Time Complexity |
| 資料番号 | |
| 発行日 |
| 研究会情報 | |
| 研究会 | ISEC |
|---|---|
| 開催期間 | 1998/5/15(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Information Security (ISEC) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | プライバシーを考慮した効果的な情報獲得 |
| サブタイトル（和） | |
| タイトル（英） | Efficient Private Information Retrieval |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 情報獲得 / Information Retrieval |
| キーワード(2)（和/英） | 通信量 / Communication Complexity |
| キーワード(3)（和/英） | 時間計算量 / Time Complexity |
| 第 1 著者 氏名（和/英） | 伊東 利哉 / TOSHIYA ITOH |
| 第 1 著者 所属（和/英） | 東京工業大学大学院総合理工学研究科物理情報工学専攻 Department of Information Processing Interdisciplinary Graduate School of Science and Engineering Tokyo Institute of Technology |
| 発表年月日 | 1998/5/15 |
| 資料番号 | |
| 巻番号（vol） | vol.98 |
| 号番号（no） | 48 |
| ページ範囲 | pp.- |
| ページ数 | 12 |
| 発行日 | |