Privately retrieve data from large databases

Authors

Qianhong Wu, University of WollongongFollow
Yi Mu, University of WollongongFollow
Willy Susilo, University of WollongongFollow
Fangguo Zhang, Sun Yat-Sen University

RIS ID

15731

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.

Abstract

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.