Yeah, the computational overhead over no-privacy retrieval will always be high. Something we point out in the paper is that this does not necessarily translate to server monetary costs; for example, on AWS, where outgoing bandwidth is expensive, using our system to stream a movie is less than 2x the monetary cost of direct, no-privacy streaming. This is because the computational costs are just very small in comparison to the bandwidth costs.

As far as more compelling applications, several folks have suggested DNS, OCSP, and certificate transparency as potential examples. Using PIR as a building block, it is also possible to build more complex systems, like metadata-private messaging (systems like ‘Pung’) and even private voice calling (systems like ‘Addra’).