Towards practical private information retrieval from homomorphic encryption

Dmitry Zhuravlev

Abstract


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


protocols, encryption, servers, complexity theory, private information retrieval, homomorphic encryption

Full Text:

PDF

References


B. Chor, E. Kushilevitz, O. Goldreich, M. Sudan, Private Information Retrieval, ACM, 45, 1998.

E. Kushilevitz, R. Ostrovsky, Replication is not needed: single database, computationally-private information retrieval, In FOCS, 1997, pp 364.

C. Gentry, A fully homomorphic encryption scheme, PhD thesis, Stanford University, 2009.

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

Z. Brakerski, V. Vaikuntanathan, Efficient fully homomorphic encryption from (standard) LWE, FOCS, 2011, pp. 97-106.

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, pp. 1125-1134.

M. Dijk, C. Gentry, S. Halevi, V. Vaikuntanathan, Fully Homomorphic Encryption over the Integers Gilbert, H., ed.: EUROCRYPT. Volume 6110 of Lecture Notes in Computer Science, Springer, 2010, pp. 24-43.

C. Dong, C. Chen, A Fast Single Server Private Information Retrieval Protocol with Low Communication Cost, ESORICS, Lecture Notes in Computer Science,

Volume 8712, 2014, pp 380-399.

Z. Brakerski, C. Gentry, V. Vaikuntanathan, (Leveled) fully homomorphic encryption without bootstrapping, ITCS, 2012, pp. 309-325.

D. Zhuravlev, I. Samoilovych, R. Orlovskyi, I. Bondarenko, Y. Lavrenyuk, Encrypted Program Execution, TrustCom, 2014.

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


Refbacks

  • There are currently no refbacks.