Hamid Mozaffari (University of Massachusetts Amherst), Amir Houmansadr (University of Massachusetts Amherst)

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 emph{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 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 $912$KB communication bandwidth on the rich server compared to $228$KB on the poor server (by contrast to $456$KB overhead on each of the servers for a traditional homogeneous design).

View More Papers

ABSynthe: Automatic Blackbox Side-channel Synthesis on Commodity Microarchitectures

Ben Gras (Vrije Universiteit Amsterdam, Intel Corporation), Cristiano Giuffrida (Vrije Universiteit Amsterdam), Michael Kurth (Vrije Universiteit Amsterdam), Herbert Bos (Vrije...

Read More

Unicorn: Runtime Provenance-Based Detector for Advanced Persistent Threats

Xueyuan Han (Harvard University), Thomas Pasquier (University of Bristol), Adam Bates (University of Illinois at Urbana-Champaign), James Mickens (Harvard University),...

Read More

Melting Pot of Origins: Compromising the Intermediary Web Services...

Takuya Watanabe (NTT), Eitaro Shioji (NTT), Mitsuaki Akiyama (NTT), Tatsuya Mori (Waseda University, NICT, and RIKEN AIP)

Read More

Dynamic Searchable Encryption with Small Client Storage

Ioannis Demertzis (University of Maryland), Javad Ghareh Chamani (Hong Kong University of Science and Technology & Sharif University of Technology),...

Read More