Heterogeneous Private Information Retrieval

—Private information retrieval (PIR) enables clients to query and retrieve data from untrusted servers without the untrusted servers learning which data was retrieved. In this paper, we present a new class of multi-server PIR protocols, which we call heterogeneous PIR (HPIR) . In such multi-server PIR protocols, the computation and communication overheads imposed on the PIR servers are non-uniform, i.e., some servers handle higher computation/communication burdens than the others. This enables heterogeneous PIR protocols to be suitable for a range of new PIR applications. What enables us to enforce such heterogeneity is a unique PIR-tailored secret sharing algorithm that we leverage in building our PIR protocol. We have implemented our HPIR protocol and evaluated its performance in comparison with regular (i.e., homogenous) PIR protocols. Our evaluations demonstrate that a querying client can trade off the computation and communication loads of the (heterogeneous) PIR servers by adjusting some parameters. For example in a two server scenario with a heterogeneity degree of 4 / 1 , to retrieve a 456 KB file from a 0 . 2 GB database, the rich (i.e., resourceful) PIR server will do 1 . 1 seconds worth of computation compared to 0 . 3 seconds by the poor (resource-constrained) PIR server; this is while each of the servers would do the same 1 seconds of computation in a homogeneous settings. Also, for this given example, our HPIR protocol will impose a 912 KB communication bandwidth on the rich server compared to 228 KB on the poor server (by contrast to 456 KB overheads on each of the servers for a traditional homogeneous design).