There’s a loophole, though. If the database is static, and people make many different queries to it, you can theoretically sneak around the badness as follows. First do one big “pre-processing” on the whole database. Then individual queries can just look at a small piece of that.
This assumes that the operator can somehow take in a public database, then (using a fully public unkeyed process) “scramble it up” so well that when someone asks for a few disk sectors, even the operator has no idea what entries are stored there.
If you asked me whether such a fully public unkeyed process was possible, my intuition would have said “no way”. Or maybe it would have said “sure, but it will imply implausibly strong cryptographic obfuscation and trusted setup.” (And some early attempts used this.)
Which brings me to the LMW DEPIR paper. What they show is that there’s an extremely “simple” form of oblivious locally-decodable code that has exactly the property you need. It’s based on Ring LWE and while it isn’t *super* efficient right now, it’s not crazy either.
The encoding scheme uses very simple ingredients: it encodes the DB into multivariate polynomial over a ring. The client then queries on a Ring LWE-encrypted index, which allows it to obtain the polynomial at that index. A clever lookup-table approach lets the server evaluate the polynomial without touching O(|DB|) bits of memory or disk.
The neat thing about this result is that it also implies that we can build fully-homomorphic encryption over RAM machines that avoids worst-case costs. Here the “database” is a computer’s RAM and nobody can see what values it accesses.
Anyway this series of tweets hardly does justice to how surprising and cool this result is. Here is the paper itself. If we look back in 30 years I think this will be one of the most significant cryptography results of our time. https://eprint.iacr.org/2022/1703
Matthew Green /
npub1jq…ys9nx
2024-09-19 18:11:49
in reply to nevent1q…gxqp
Author Public Key
npub1jqdp6zu2wk55xnheffg0xhp96p6jv634s24uafaz66rhzpjw944q7ys9nxPublished at
2024-09-19 18:11:49Event JSON
{
"id": "1715f7d9175e1c65191539487f083643a25e0a2b983eede43b9b7a316b7fb85c",
"pubkey": "901a1d0b8a75a9434ef94a50f35c25d075266a3582abcea7a2d68771064e2d6a",
"created_at": 1726769509,
"kind": 1,
"tags": [
[
"e",
"921389dc04297b10e3ab9039544a56dc0a8cc3620cc68620aa5995dabff1e1e8",
"wss://nostr.sprovoost.nl",
"reply"
],
[
"proxy",
"https://ioc.exchange/users/matthew_d_green/statuses/113165566546320649",
"activitypub"
]
],
"content": "There’s a loophole, though. If the database is static, and people make many different queries to it, you can theoretically sneak around the badness as follows. First do one big “pre-processing” on the whole database. Then individual queries can just look at a small piece of that.\n\nThis assumes that the operator can somehow take in a public database, then (using a fully public unkeyed process) “scramble it up” so well that when someone asks for a few disk sectors, even the operator has no idea what entries are stored there.\n\nIf you asked me whether such a fully public unkeyed process was possible, my intuition would have said “no way”. Or maybe it would have said “sure, but it will imply implausibly strong cryptographic obfuscation and trusted setup.” (And some early attempts used this.)\n\nWhich brings me to the LMW DEPIR paper. What they show is that there’s an extremely “simple” form of oblivious locally-decodable code that has exactly the property you need. It’s based on Ring LWE and while it isn’t *super* efficient right now, it’s not crazy either.\n\nThe encoding scheme uses very simple ingredients: it encodes the DB into multivariate polynomial over a ring. The client then queries on a Ring LWE-encrypted index, which allows it to obtain the polynomial at that index. A clever lookup-table approach lets the server evaluate the polynomial without touching O(|DB|) bits of memory or disk.\n\nThe neat thing about this result is that it also implies that we can build fully-homomorphic encryption over RAM machines that avoids worst-case costs. Here the “database” is a computer’s RAM and nobody can see what values it accesses.\n\nAnyway this series of tweets hardly does justice to how surprising and cool this result is. Here is the paper itself. If we look back in 30 years I think this will be one of the most significant cryptography results of our time. https://eprint.iacr.org/2022/1703",
"sig": "440221ade9bc5b398ab288d00cdbade206832c485168dc1f359a01fe95425a4c5b125c2ff9a6bf4c8dfc6ecb80d25f9cfb31a0ccbcdd96e886269ec71a6e8ba0"
}