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.)
Matthew Green /
npub1jq…ys9nx
2024-09-19 18:09:44
in reply to nevent1q…x6fg
Author Public Key
npub1jqdp6zu2wk55xnheffg0xhp96p6jv634s24uafaz66rhzpjw944q7ys9nxPublished at
2024-09-19 18:09:44Event JSON
{
"id": "921389dc04297b10e3ab9039544a56dc0a8cc3620cc68620aa5995dabff1e1e8",
"pubkey": "901a1d0b8a75a9434ef94a50f35c25d075266a3582abcea7a2d68771064e2d6a",
"created_at": 1726769384,
"kind": 1,
"tags": [
[
"e",
"f4aa30d21716c84b0c7d3a60142fed57007269aa5ed0d939e5dc5990a658f267",
"wss://nostr.sprovoost.nl",
"reply"
],
[
"proxy",
"https://ioc.exchange/users/matthew_d_green/statuses/113165558356701657",
"activitypub"
]
],
"content": "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 \u0026 without it having to touch every item in the DB each time.\n\nShort 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.\n\nThink 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.\n\nThe 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.\n\nAfter 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.\n\n(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.)",
"sig": "4e8dac1df8709ba9761425e58c13e2d40283f03e6ef122488333ecfe198528925388daf1c7a13ed2c4ff784a0e189783390170cb8e2042bcbdac8f36019e22cf"
}