Geodesic
The order of communication complexity of PIR-protocols
Diskretnaya Matematika, Tome 20 (2008) no. 3, pp. 136-146

Voir la notice de l'article provenant de la source Math-Net.Ru

Private information retrieval protocols (PIR-protocols) allow a user to get the desired bit of information from a database whose copy is stored in several non-linked servers in such a way that the administrators of the database know nothing about the index of the bit the user requests for. The communication complexity of a protocol is defined as the total number of the bits exchanged between the user and the servers in the protocol. In this paper, we find the order of communication complexity of PIR-protocols depending on the degree of essentiality of the server response functions. 
@article{DM_2008_20_3_a12,
     author = {G. A. Mailybaeva},
     title = {The order of communication complexity of {PIR-protocols}},
     journal = {Diskretnaya Matematika},
     pages = {136--146},
     publisher = {mathdoc},
     volume = {20},
     number = {3},
     year = {2008},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2008_20_3_a12/}
}
TY  - JOUR
AU  - G. A. Mailybaeva
TI  - The order of communication complexity of PIR-protocols
JO  - Diskretnaya Matematika
PY  - 2008
SP  - 136
EP  - 146
VL  - 20
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2008_20_3_a12/
LA  - ru
ID  - DM_2008_20_3_a12
ER  - 
%0 Journal Article
%A G. A. Mailybaeva
%T The order of communication complexity of PIR-protocols
%J Diskretnaya Matematika
%D 2008
%P 136-146
%V 20
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2008_20_3_a12/
%G ru
%F DM_2008_20_3_a12
G. A. Mailybaeva. The order of communication complexity of PIR-protocols. Diskretnaya Matematika, Tome 20 (2008) no. 3, pp. 136-146. http://geodesic.mathdoc.fr/item/DM_2008_20_3_a12/