The search functionality is under construction.

The search functionality is under construction.

Private information retrieval for *k* *k*,*l*)-PIR for short) is a protocol that (1) a user sends an *l* tuple query to each of *k* noncommunicating replicated databases; (2) each database responds the user with an answer corresponding to the *l* tuple query; (3) the user privately retrieve any single bit out of the *n* bits of data stored in *k* databases. 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 wishes to get. In general, the efficiency of (*k*,*l*)-PIR is measured by the total amount of bits exchanged between the user and the *k* databases, but few about its lower bounds are known except for restricted cases. In this paper, we classify (*k*,*l*)-PIR into a *linear* type, a *multilinear* type, and an *affine* type with respect to the relationship between queries to each database (made by the user) and answers to the user (made by each database), and show that (1) the lower bound for the communication complexity of any multilinear type (*k*,*l*)-PIR is Ω(*n*^{1/(l+1)}) (Theorem 3.1); (2) the lower bound for the communication complexity of any linear type (*k*,*l*)-PIR is Ω(*n*) (Corollary 3.2); (3) the lower bound for the communication complexity of any affine type (*k*,*l*)-PIR is Ω(*n*^{1/(l+1)}) (Theorem 4.2).

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E84-A No.1 pp.157-164

- Publication Date
- 2001/01/01

- 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, "On Lower Bounds for the Communication Complexity of Private Information Retrieval" in IEICE TRANSACTIONS on Fundamentals,
vol. E84-A, no. 1, pp. 157-164, January 2001, doi: .

Abstract: Private information retrieval for *k* *k*,*l*)-PIR for short) is a protocol that (1) a user sends an *l* tuple query to each of *k* noncommunicating replicated databases; (2) each database responds the user with an answer corresponding to the *l* tuple query; (3) the user privately retrieve any single bit out of the *n* bits of data stored in *k* databases. 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 wishes to get. In general, the efficiency of (*k*,*l*)-PIR is measured by the total amount of bits exchanged between the user and the *k* databases, but few about its lower bounds are known except for restricted cases. In this paper, we classify (*k*,*l*)-PIR into a *linear* type, a *multilinear* type, and an *affine* type with respect to the relationship between queries to each database (made by the user) and answers to the user (made by each database), and show that (1) the lower bound for the communication complexity of any multilinear type (*k*,*l*)-PIR is Ω(*n*^{1/(l+1)}) (Theorem 3.1); (2) the lower bound for the communication complexity of any linear type (*k*,*l*)-PIR is Ω(*n*) (Corollary 3.2); (3) the lower bound for the communication complexity of any affine type (*k*,*l*)-PIR is Ω(*n*^{1/(l+1)}) (Theorem 4.2).

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e84-a_1_157/_p

Copy

@ARTICLE{e84-a_1_157,

author={Toshiya ITOH, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={On Lower Bounds for the Communication Complexity of Private Information Retrieval},

year={2001},

volume={E84-A},

number={1},

pages={157-164},

abstract={Private information retrieval for *k* *k*,*l*)-PIR for short) is a protocol that (1) a user sends an *l* tuple query to each of *k* noncommunicating replicated databases; (2) each database responds the user with an answer corresponding to the *l* tuple query; (3) the user privately retrieve any single bit out of the *n* bits of data stored in *k* databases. 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 wishes to get. In general, the efficiency of (*k*,*l*)-PIR is measured by the total amount of bits exchanged between the user and the *k* databases, but few about its lower bounds are known except for restricted cases. In this paper, we classify (*k*,*l*)-PIR into a *linear* type, a *multilinear* type, and an *affine* type with respect to the relationship between queries to each database (made by the user) and answers to the user (made by each database), and show that (1) the lower bound for the communication complexity of any multilinear type (*k*,*l*)-PIR is Ω(*n*^{1/(l+1)}) (Theorem 3.1); (2) the lower bound for the communication complexity of any linear type (*k*,*l*)-PIR is Ω(*n*) (Corollary 3.2); (3) the lower bound for the communication complexity of any affine type (*k*,*l*)-PIR is Ω(*n*^{1/(l+1)}) (Theorem 4.2).

keywords={},

doi={},

ISSN={},

month={January},}

Copy

TY - JOUR

TI - On Lower Bounds for the Communication Complexity of Private Information Retrieval

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 157

EP - 164

AU - Toshiya ITOH

PY - 2001

DO -

JO - IEICE TRANSACTIONS on Fundamentals

SN -

VL - E84-A

IS - 1

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - January 2001

AB - Private information retrieval for *k* *k*,*l*)-PIR for short) is a protocol that (1) a user sends an *l* tuple query to each of *k* noncommunicating replicated databases; (2) each database responds the user with an answer corresponding to the *l* tuple query; (3) the user privately retrieve any single bit out of the *n* bits of data stored in *k* databases. 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 wishes to get. In general, the efficiency of (*k*,*l*)-PIR is measured by the total amount of bits exchanged between the user and the *k* databases, but few about its lower bounds are known except for restricted cases. In this paper, we classify (*k*,*l*)-PIR into a *linear* type, a *multilinear* type, and an *affine* type with respect to the relationship between queries to each database (made by the user) and answers to the user (made by each database), and show that (1) the lower bound for the communication complexity of any multilinear type (*k*,*l*)-PIR is Ω(*n*^{1/(l+1)}) (Theorem 3.1); (2) the lower bound for the communication complexity of any linear type (*k*,*l*)-PIR is Ω(*n*) (Corollary 3.2); (3) the lower bound for the communication complexity of any affine type (*k*,*l*)-PIR is Ω(*n*^{1/(l+1)}) (Theorem 4.2).

ER -