Single-Database Private Information Retrieval from Fully Homomorphic Encryption

Full text for this resource is not available from the Research Repository.

Yi, Xun, Kaosar, Md. Golam, Paulet, Russell and Bertino, Elisa (2012) Single-Database Private Information Retrieval from Fully Homomorphic Encryption. IEEE Transactions on Knowledge and Data Engineering, 25 (5). pp. 1125-1134. ISSN 1041-4347


Private Information Retrieval (PIR) allows a user to retrieve the $(i)$th bit of an $(n)$-bit database without revealing to the database server the value of $(i)$. In this paper, we present a PIR protocol with the communication complexity of $(O(gamma log n))$ bits, where $(gamma)$ is the ciphertext size. Furthermore, we extend the PIR protocol to a private block retrieval (PBR) protocol, a natural and more practical extension of PIR in which the user retrieves a block of bits, instead of retrieving single bit. Our protocols are built on the state-of-the-art fully homomorphic encryption (FHE) techniques and provide privacy for the user if the underlying FHE scheme is semantically secure. The total communication complexity of our PBR is $(O(gamma log m+gamma n/m))$ bits, where $(m)$ is the number of blocks. The total computation complexity of our PBR is $(O(mlog m))$ modular multiplications plus $(O(n/2))$ modular additions. In terms of total protocol execution time, our PBR protocol is more efficient than existing PBR protocols which usually require to compute $(O(n/2))$ modular multiplications when the size of a block in the database is large and a high-speed network is available.

Dimensions Badge

Altmetric Badge

Item type Article
DOI 10.1109/TKDE.2012.90
Official URL
Subjects Historical > FOR Classification > 0806 Information Systems
Current > Division/Research > College of Science and Engineering
Keywords ResPubID26716, private information retrieval, private block retrieval, fully homomorphic encryption
Citations in Scopus 64 - View on Scopus
Download/View statistics View download statistics for this item

Search Google Scholar

Repository staff login