For Full-Text 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
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Vol.E82-A No.1 pp.11-20
Publication Date: 1999/01/25
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
information retrieval, privacy, communication complexity, time complexity, covering codes,
Full Text: PDF>>
Informally, private information retrieval for k 1 databases (k-PIR) 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 2-PIR with communication complexity 12 n1/32 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 ckn1/(2k-1) some constant ck > 0. In this paper, we relax the condition for the covering codes and present time-efficient 2-PIR with communication complexity 12 n1/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 ck' n1/(2k-1) for some constant ck' << ck.