A Fast Multi-Server, Multi-Block Private Information Retrieval Protocol

Private Information Retrieval (PIR) allows users to retrieve information from a database without revealing the content of these queries to anyone. The traditional information-theoretic PIR schemes utilize multiple servers to download single data block, thus incur high communication overhead and high computation burden. In this paper, we develop an Information- theoretic multi-block PIR scheme that significantly reduce the client communication and computation overheads by downloading multiple data blocks at a time. The design of k-safe binary matrices insures the information will not be revealed even if up to k servers collude. Our scheme has much lower overhead than the classic PIR schemes. The implementation of fast XOR operations benefits both servers and clients in reducing coding and decoding time. Our work demonstrates that multi-block PIR scheme can be optimized to simultaneously achieve low communication and computation overhead, comparable to even non-PIR systems, while maintaining a high level of privacy.