Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

Single-Database private information retrieval from fully homomorphic encryption

Yi, X., Kaosar, M.G., Paulet, R. and Bertino, E. (2013) Single-Database private information retrieval from fully homomorphic encryption. IEEE Transactions on Knowledge and Data Engineering, 25 (5). pp. 1125-1134.

Link to Published Version:
*Subscription may be required


Private Information Retrieval (PIR) allows a user to retrieve the ith 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(γ logn) bits, where -y 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(γ logm + γn/m) bits, where m is the number of blocks. The total computation complexity of our PBR is O(m logm) 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: Journal Article
Publisher: IEEE
Copyright: © 2021 IEEE
Item Control Page Item Control Page