Geodesic
Towards practical private information retrieval from homomorphic encryption
Algebra and discrete mathematics, Tome 19 (2015) no. 2, pp. 302-312.

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

Private information retrieval (PIR) allows a client to retrieve data from a remote database while hiding the client's access pattern. To be applicable for practical usage, PIR protocol should have low communication and computational costs. In this paper a new generic PIR protocol based on somewhat homomorphic encryption (SWHE) is proposed. Compared to existing constructions the proposed scheme has reduced multiplicative depth of the homomorphic evaluation circuit which allows to cut down the total overhead in schemes with ciphertext expansion. The construction results in a system with $O(\log{n})$ communication cost and $O(n)$ computational complexity for a database of size $n$.
Keywords: encryption, servers, complexity theory, private information retrieval, homomorphic encryption.
Mots-clés : protocols 
@article{ADM_2015_19_2_a12,
     author = {Dmitry Zhuravlev},
     title = {Towards practical private information retrieval from homomorphic encryption},
     journal = {Algebra and discrete mathematics},
     pages = {302--312},
     publisher = {mathdoc},
     volume = {19},
     number = {2},
     year = {2015},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ADM_2015_19_2_a12/}
}
TY  - JOUR
AU  - Dmitry Zhuravlev
TI  - Towards practical private information retrieval from homomorphic encryption
JO  - Algebra and discrete mathematics
PY  - 2015
SP  - 302
EP  - 312
VL  - 19
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ADM_2015_19_2_a12/
LA  - en
ID  - ADM_2015_19_2_a12
ER  - 
%0 Journal Article
%A Dmitry Zhuravlev
%T Towards practical private information retrieval from homomorphic encryption
%J Algebra and discrete mathematics
%D 2015
%P 302-312
%V 19
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ADM_2015_19_2_a12/
%G en
%F ADM_2015_19_2_a12
Dmitry Zhuravlev. Towards practical private information retrieval from homomorphic encryption. Algebra and discrete mathematics, Tome 19 (2015) no. 2, pp. 302-312. http://geodesic.mathdoc.fr/item/ADM_2015_19_2_a12/

[1] B. Chor, E. Kushilevitz, O. Goldreich, M. Sudan, Private Information Retrieval, ACM, 45, 1998 | MR | Zbl

[2] E. Kushilevitz, R. Ostrovsky, “Replication is not needed: single database, computationally-private information retrieval”, FOCS, 1997, 364

[3] C. Gentry, A fully homomorphic encryption scheme, PhD thesis, Stanford University, 2009 | Zbl

[4] K. Lauter, M. Naehrig, V. Vaikuntanathan, “Can homomorphic encryption be practical?”, Technical Report MSR-TR-2011-61, Microsoft Research, 2011

[5] Z. Brakerski, V. Vaikuntanathan, “Efficient fully homomorphic encryption from (standard) LWE”, FOCS, 2011, 97–106 | MR | Zbl

[6] X. Yi, M. Kaosar, R. Paulet, E. Bertino, “Single-database private information retrieval from fully homomorphic encryption”, IEEE Trans. Knowl. Data Eng., 25:5 (2013), 1125–1134 | DOI

[7] M. Dijk, C. Gentry, S. Halevi, V. Vaikuntanathan, “Fully Homomorphic Encryption over the Integers”, Advances in Cryptology — EUROCRYPT 2010, Lecture Notes in Computer Science, 6110, ed. Gilbert H., Springer, 2010, 24–43 | DOI | MR | Zbl

[8] C. Dong, C. Chen, “A Fast Single Server Private Information Retrieval Protocol with Low Communication Cost”, ESORICS, Lecture Notes in Computer Science, 8712, 2014, 380–399 | DOI

[9] Z. Brakerski, C. Gentry, V. Vaikuntanathan, “(Leveled) fully homomorphic encryption without bootstrapping”, ITCS, 2012, 309–325 | DOI | MR

[10] D. Zhuravlev, I. Samoilovych, R. Orlovskyi, I. Bondarenko, Y. Lavrenyuk, “Encrypted Program Execution”, TrustCom, 2014, 817–822

[11] Y. Tian, M. Al-Rodhaan, B. Song, A. Al-Dhelaan, H. Ma, “Somewhat homomorphic cryptography for matrix multiplication using GPU acceleration”, ISBAST, 2014