
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Efficient Private Information Retrieval
Toshiya ITOH
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E82A
No.1
pp.1120 Publication Date: 1999/01/25
Online ISSN:
DOI:
Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security) Category: Keyword: information retrieval, privacy, communication complexity, time complexity, covering codes,
Full Text: PDF>>
Summary:
Informally, private information retrieval for k 1 databases (kPIR) is an interactive 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 2PIR with communication complexity 12 n^{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 kPIR with communication complexity at most c_{k}n^{1/(2k1)} some constant c_{k} > 0. In this paper, we relax the condition for the covering codes and present timeefficient 2PIR with communication complexity 12 n^{1/3}. In addition, we generally formulate the recursive scheme by Ambainis and show that for each k 4, there exists kPIR with communication complexity at most c_{k}' n^{1/(2k1)} for some constant c_{k}' << c_{k}.

