Helger Lipmaa's publications

Two New Efficient PIR-Writing Protocols

Helger Lipmaa and Bingsheng Zhang. Two New Efficient PIR-Writing Protocols. In Jianying Zhou and Moti Yung?, editors, ACNS 2010, volume 6123 of Lecture Notes in Computer Science, pages 438--455, Beijing, China, June 22--25, 2010. Springer, Heidelberg.

File: [.pdf (210 KB)] pdf recommended.


Assume that a client outsources his database to a remote storage-provider (the server), so that for privacy reasons, the client's database is encrypted by his secret key. During a PIR-writing protocol, the client updates one element of the encrypted database without revealing to the semi-honest server which element was updated and, of course, to which value. The best previous PIR-writing protocols had square-root communication complexity. In this paper, we propose two new PIR-writing protocols. The first one can be based on (say) the Damg{\aa}rd-Jurik additively homomorphic public-key cryptosystem, and it has (amortized) polylogarithmic communication for a limited number of updates. The second one is based on a fully-homomorphic public-key cryptosystem, a much stronger primitive, but it achieves optimal logarithmic communication..

Keywords: Cryptocomputing, binary decision diagram, circuits, fully-homomorphic encryption, PIR-writing, PrivateBDD.


Page by Helger Lipmaa. Send your inqueries to <helger.lipmaa><at>gmail.com.