One of the most surprising privacy results of the last 5 years is the LMW “doubly efficient PIR” paper. The basic idea is that I can load an item from a public database without the operator seeing which item I’m loading & without it having to touch every item in the DB each time.

Short background: Private Information Retrieval isn’t a new idea. It lets me load items from a (remote) public database without the operator learning what item I’m asking for. But traditionally there’s a *huge* performance hit for doing this.

Think about it this way: if the database is public and you’re the operator, then if I ask for entry #22: no matter what crypto we use, you’re going to know which sectors on disk you read from. If it’s a small subset, you can just query yourself on every file til you find one that matches.

The only way to get around this (apparently) is for the crypto protocol to make the operator read and compute over *every single* file on disk just to serve one file. This sucks. And at a high level, it seems to indicate that a “private Internet” will always suck.

After all: the Internet is mostly loading stuff from servers. Computing is mostly loading stuff from RAM or disk. If we want to make those loads happen privately, then every single one (intuitively) now has to have the same cost as reading everything. Yuck.

(Imagine trying to stream “A Christmas Prince” on Netflix, but not wanting anyone to know you have bad taste. To serve this privately, the server has to load and calculate over every single movie in the Netflix catalog! That’s going to be terrible.)