Single-Database Private Information Retrieval from Fully Homomorphic Encryption


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(m\log 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.


Protocols, Encryption, Servers, Complexity theory, Indexes, fully homomorphic encryption, Private information retrieval, private block retrieval

Date of this Version





IEEE Transactions on Knowledge and Data Engineering

May 2013 (vol. 25 no. 5)
pp. 1125-1134