Geodesic
Private information retrieval protocol
Matematičeskie voprosy kriptografii, Tome 6 (2015), pp. 5-21.

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

A new computationally efficient private information retrieval protocol is proposed. It is based on coset properties of Galois groups of the field $\mathrm{GF}(q)$ finite extensions. The proposed protocol has communication complexity slightly worse than the best known schemes based on locally decodable codes and it may be constructed for any system parameters (as opposed to codes). In comparison with similar solutions based on polynomials the computational complexity of our method is smaller which is important especially for servers processing multiple requests from multiple users. 
@article{MVK_2015_6_a0,
     author = {A. V. Afanasieva and V. B. Balakirskii and S. V. Bezzateev},
     title = {Private information retrieval protocol},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {5--21},
     publisher = {mathdoc},
     volume = {6},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MVK_2015_6_a0/}
}
TY  - JOUR
AU  - A. V. Afanasieva
AU  - V. B. Balakirskii
AU  - S. V. Bezzateev
TI  - Private information retrieval protocol
JO  - Matematičeskie voprosy kriptografii
PY  - 2015
SP  - 5
EP  - 21
VL  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MVK_2015_6_a0/
LA  - ru
ID  - MVK_2015_6_a0
ER  - 
%0 Journal Article
%A A. V. Afanasieva
%A V. B. Balakirskii
%A S. V. Bezzateev
%T Private information retrieval protocol
%J Matematičeskie voprosy kriptografii
%D 2015
%P 5-21
%V 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MVK_2015_6_a0/
%G ru
%F MVK_2015_6_a0
A. V. Afanasieva; V. B. Balakirskii; S. V. Bezzateev. Private information retrieval protocol. Matematičeskie voprosy kriptografii, Tome 6 (2015), pp. 5-21. http://geodesic.mathdoc.fr/item/MVK_2015_6_a0/

[1] Woodruff D., Yekhanin S., “A geometric approach to information-theoretic private information retrieval”, SIAM J. Comput., 37:4 (2007), 1046–1056 | DOI | MR | Zbl

[2] Chor B., Kushilevitz E., Goldreich O., Sudan M., “Private information retrieval”, Proc. 36th Annu. IEEE Symp. on Foundations of Computer Science, 1995, 41–50 | DOI

[3] Chor B., Gilboa N., “Computationally private information retrieval”, 29th STOC, 1997, 304–313

[4] Kushilevitz E., Ostrovsky R., “Replication is not needed: Single database, computationally-private information retrieval”, Proc. of the 38th Annu. IEEE Symp. on Foundations of Computer Science, 1997, 364–373 | DOI

[5] Ostrovsky R. et al., Method and apparatus for private information retrieval from a single electronic storage device, US Patent 6167392

[6] Cachin C., Micali S., Stadler M., “Computationally Private Information Retrieval with Polylogarithmic Communication”, Proceedings of EUROCRYPT' 99, Lect. Notes Comput. Sci., 1592, 1999, 402–414 | DOI | Zbl

[7] Gentry C., Ramzan Z., “Single-database private information retrieval with constant communication rate”, ICALP: Annu. Int. Colloq. on Automata, Languages and Programming, 2005, 803–815 | MR | Zbl

[8] Ramzan et al., Method and apparatus for communication efficient private information retrieval and oblivious transfer, US Patent 8065332 B2

[9] Groth J., Kiayias A., Lipmaa H., “Multi-query computationally-private information retrieval with constant communication rate”, Practice and Theory in Public Key Cryptography – PKC 2010, Lect. Notes Comput. Sci., 6056, 2010, 107–123 | DOI | MR | Zbl

[10] Melchor C. A., Gaborit P., A lattice-based computationally-efficient private information retrieval protocol, , 2007 http://eprint.iacr.org/2007/446.pdf

[11] Beimel A., Ishai Y., Kushilevitz E., “General constructions for information-theoretic private information retrieval”, J. Comput. Syst. Sci., 71 (2005), 213–247 | DOI | MR | Zbl

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

[13] Yekhanin S., “Locally decodable codes”, Foundations and Trends in Theoretical Computer Science, 7:1 (2011), 1–117 | MR

[14] Mak-Vilyams F. Dzh., Sloen N. Dzh., Teoriya kodov, ispravlyayuschikh oshibki, Svyaz, M., 1979

[15] Landau E., Handbuch der Lehre yon der Verteilung der Primzahlen, v. 1, Reprinted in 1953 by Chelsea Publishing Co., New York, Teubner, Leipzig, 1909 | MR

[16] Rosser J. B., Schoenfeld L., “Approximate formulas for some functions of prime numbers”, Illinois J. Math., 6:1 (1962), 64–94 | MR | Zbl

[17] Shennon K., Raboty po teorii informatsii i kibernetike, Inostr. lit., M., 1963