Parallel, scalable and bandwidth-optimized computational private information retrieval

Official URL: http://risc01.sabanciuniv.edu/record=b1589815 (Table of Contents)

With the current increase of interest in cloud computing, the security of user data stored in remote servers has become an important concern. Hiding access patterns of clients can be crucial in particular applications such as stock market or patent databases. Private Information Retrieval (PIR) is proposed to enable a client to retrieve a file stored in a cloud server without revealing the queried file to the server. In this work, we offer improvements to BddCpir, which is a PIR protocol proposed by Lipmaa. The original BddCpir uses Binary Decision Diagrams (BDD) as the data structure, where data items are stored at the sink nodes of the tree. First of all, we offer the usage of quadratic and octal trees instead, where every non-sink node has four and eight child nodes, respectively, to reduce the depth of the tree. By adopting more shallow trees, we obtain an improved server implementation which is an order of magnitude faster than the original scheme, without changing the asymptotic complexity. Secondly, we suggest a non-trivial parallelization method that takes advantage of the shared-memory multi-core architectures to further decrease server computation latencies. Finally, we show how to scale the PIR scheme for larger database sizes with only a small overhead in bandwidth complexity, with the utilization of shared-memory many-core processors. Consequently, we show how our scheme is bandwidth-efficient in terms of the data being exchanged in a run of the CPIR protocol, in proportion to the database size.