| Presentation | 1998/5/15 Efficient Private Information Retrieval TOSHIYA ITOH, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Information Retrieval / Communication Complexity / Time Complexity |
| Paper # | |
| Date of Issue |
| Conference Information | |
| Committee | ISEC |
|---|---|
| Conference Date | 1998/5/15(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Information Security (ISEC) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Efficient Private Information Retrieval |
| Sub Title (in English) | |
| Keyword(1) | Information Retrieval |
| Keyword(2) | Communication Complexity |
| Keyword(3) | Time Complexity |
| 1st Author's Name | TOSHIYA ITOH |
| 1st Author's Affiliation | Department of Information Processing Interdisciplinary Graduate School of Science and Engineering Tokyo Institute of Technology() |
| Date | 1998/5/15 |
| Paper # | |
| Volume (vol) | vol.98 |
| Number (no) | 48 |
| Page | pp.pp.- |
| #Pages | 12 |
| Date of Issue | |