Outsourced Private Information Retrieval with Pricing and Access Control

We propose a scheme for outsourcing Private Informa-tion Retrieval (PIR) to untrusted servers while protect-ing the privacy of the database owner as well as that of the database clients. We observe that by layering PIR on top of an Oblivious RAM (ORAM) data layout, we provide the ability for the database owner to perform private writes, while database clients can perform pri-vate reads from the database even while the owner is offline. We can also enforce pricing and access control on a per-record basis for these reads. This extends the usual ORAM model by allowing multiple database read-ers without requiring trusted hardware; indeed, almost all of the computation in our scheme during reads is per-formed by untrusted cloud servers. We implement a real system as a proof of concept. Our system privately up-dates a 1 MB record in a 2 GB database with an average end-to-end overhead of 1.65 seconds and answers a PIR query within 3.5 seconds.