Research Repository

Single-Database Private Information Retrieval from Fully Homomorphic Encryption

Yi, Xun and Kaosar, Md. Golam and Paulet, Russell and Bertino, E (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

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

Abstract

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.

Item Type: Article
Uncontrolled Keywords: ResPubID26716, private information retrieval, private block retrieval, fully homomorphic encryption
Subjects: FOR Classification > 0806 Information Systems
Faculty/School/Research Centre/Department > College of Science and Engineering
Depositing User: Ms Phung.T Tran
Date Deposited: 04 Apr 2014 00:41
Last Modified: 24 Sep 2014 02:01
URI: http://vuir.vu.edu.au/id/eprint/23671
DOI: 10.1109/TKDE.2012.90
ePrint Statistics: View download statistics for this item
Citations in Scopus: 0 - View on Scopus

Repository staff only

View Item View Item

Search Google Scholar