The search functionality is under construction.

The search functionality is under construction.

Informally, private information retrieval for *k* *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 *n*^{1/3}*k* *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 12 *n*^{1/3}. In addition, we generally formulate the recursive scheme by Ambainis and show that for each *k* *k*-PIR with communication complexity at most *c*_{k}' *n*^{1/(2k-1)} for some constant *c*_{k}' << *c*_{k}.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E82-A No.1 pp.11-20

- Publication Date
- 1999/01/25

- Publicized

- Online ISSN

- DOI

- Type of Manuscript
- Special Section PAPER (Special Section on Cryptography and Information Security)

- Category

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Toshiya ITOH, "Efficient Private Information Retrieval" in IEICE TRANSACTIONS on Fundamentals,
vol. E82-A, no. 1, pp. 11-20, January 1999, doi: .

Abstract: Informally, private information retrieval for *k* *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 *n*^{1/3}*k* *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 12 *n*^{1/3}. In addition, we generally formulate the recursive scheme by Ambainis and show that for each *k* *k*-PIR with communication complexity at most *c*_{k}' *n*^{1/(2k-1)} for some constant *c*_{k}' << *c*_{k}.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e82-a_1_11/_p

Copy

@ARTICLE{e82-a_1_11,

author={Toshiya ITOH, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={Efficient Private Information Retrieval},

year={1999},

volume={E82-A},

number={1},

pages={11-20},

abstract={Informally, private information retrieval for *k* *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 *n*^{1/3}*k* *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 12 *n*^{1/3}. In addition, we generally formulate the recursive scheme by Ambainis and show that for each *k* *k*-PIR with communication complexity at most *c*_{k}' *n*^{1/(2k-1)} for some constant *c*_{k}' << *c*_{k}.

keywords={},

doi={},

ISSN={},

month={January},}

Copy

TY - JOUR

TI - Efficient Private Information Retrieval

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 11

EP - 20

AU - Toshiya ITOH

PY - 1999

DO -

JO - IEICE TRANSACTIONS on Fundamentals

SN -

VL - E82-A

IS - 1

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - January 1999

AB - Informally, private information retrieval for *k* *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 *n*^{1/3}*k* *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 12 *n*^{1/3}. In addition, we generally formulate the recursive scheme by Ambainis and show that for each *k* *k*-PIR with communication complexity at most *c*_{k}' *n*^{1/(2k-1)} for some constant *c*_{k}' << *c*_{k}.

ER -