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/

[1] Chor B., Goldreich O., Kushilevitz E., Sudan M., “Private information retrieval”, Proc. 36th IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, 1995, 41–51 | Zbl

[2] Beimel A., Ishai Y., Kushilevitz E., Raymond J.-F., “Breaking the $O(n^{1/(2k-1)})$ barrier for information-theoretic private information retrieval”, Proc. 43rd IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, 2002, 261–270

[3] Yekhanin S., “New locally decodable codes and private information retrieval schemes”, Electronic Colloquium on Computational Complexity, 2006, TR06-127

[4] Goldreich O., Karloff H., Schulman L., Trevisan L., “Lower bounds for linear locally decodable codes and private information retrieval systems”, Proc. 17th IEEE Conference on Computational Complexity, IEEE Computer Society Press, 2002, 175–183

[5] Chor B., Goldreich O., Kushilevitz E., Sudan M., “Private information retrieval”, J. ACM, 45 (1998), 965–981 | DOI | MR

[6] Kerendis I., de Wolf R., “Exponential lower bound for 2-query locally decodable codes”, Proc. 35th ACM Symposium on Theory of Computing, ACM, 2003, 106–115

[7] Beigel R., Fortnow L., Gasarch W., “A nearly tight lower bound for private information retrieval protocols”, Electronic Colloquium on Computational Complexity, 2003, TR03-087

[8] Itoh T., “On lower bounds for the communication complexity of private information retrieval”, IEICE Trans. Fundamentals of Electronics, Commun. and Comp. Sci., ES4-A:1 (2001), 157–164

[9] Razborov A., Yekhanin S., “An $\Omega(n^{1/3})$ lower bound for bilinear group based private information retrieval”, Electronic Colloquium on Computational Complexity, 2006, TR06-050 | MR

[10] Gasanov E. E., Mailybaeva G. A., “Dostup k bazam dannykh bez raskrytiya zaprosa”, Matematika i bezopasnost informatsionnykh tekhnologii, Materialy konferentsii v MGU 23–24 oktyabrya 2003 g., MTsNMO, Moskva, 2004, 393–395

[11] Mailybaeva G. A., “Granitsy vyrozhdennosti protokolov dostupa k dannym bez raskrytiya zaprosa”, Diskretnaya matematika, 18:2 (2006), 98–110 | MR | Zbl