Privately retrieve data from large databases



Publication Details

Wu, Q., Mu, Y., Susilo, W. & Zhang, F. (2006). Privately retrieve data from large databases. In K. Chen, R. Deng, X. Lai & J. Zhou (Eds.), Information Security Practice and Experience Conference (pp. 367-378). Germany: Springer-Verlag.


We propose a general efficient transformation from Private Information Retrieval (PIR) to Symmetrically Private Information Retrieval (SPIR). Unlike existing schemes using inefficient zero-knowledge proofs, our transformation exploits an efficient construction of Oblivious Transfer (OT) to reduce the communication complexity which is a main goal of PIR and SPIR. The proposed SPIR enjoys almost the same communication complexity as the underlying PIR. As an independent interest, we propose a novel homomorphic public-key cryptosytem derived from Okamoto-Uchiyama cryptosystem and prove its security. The new homomorphic cryptosystem has an additional useful advantage to enable one to encrypt messages in changeable size with fixed extension bits. Based on the proposed cryptosystem, the implementation of PIR/SPIR makes PIR and SPIR applicable to large databases.

Please refer to publisher version or contact your library.



Link to publisher version (DOI)