On private information retrieval supporting range queries

Private information retrieval (PIR) allows a client to retrieve data from a database without the database server learning what data are being retrieved. Although many PIR schemes have been proposed in the literature, almost all of these focus on retrieval of a single database element, and do not consider more flexible retrieval queries such as basic range queries. Furthermore, while practically-oriented database schemes aiming at providing flexible and privacy-preserving queries have been proposed, to the best of our knowledge, no formal treatment of range queries has been considered for these. In this paper, we firstly highlight that a simple extension of the standard PIR security notion to range queries is insufficient in many usage scenarios, and propose a stronger security notion aimed at addressing this. We then show a simple generic construction of a PIR scheme meeting our stronger security notion, and propose a more efficient direct construction based on function secret sharing—while the former has a round complexity logarithmic in the size of the database, the round complexity of the latter is constant. After that, we report on the practical performance of our direct construction. Finally, we extend the results to the case of multi-dimensional databases and show the construction of PIR scheme supporting multi-dimensional range queries. The communication round complexity of our scheme is \(O(k\log n)\) in worst case, where n is the size of database and k is the number of elements retrieved by the query.