Matthew Green / is on Nostr

I teach cryptography at Johns Hopkins. https://blog.cryptographyengineering.com (#matthew_d_green on the other site.)

Last Notes

2024-10-31 13:08:35

More on that quantum cryptanalysis paper from China. https://arstechnica.com/information-technology/2024/10/the-sad-bizarre-tale-of-hype-fueling-fears-that-modern-cryptography-is-dead/

2024-09-26 11:57:31

More than you ever wanted to know about the FIPS compliance of HKDF. https://words.filippo.io/dispatches/fips-hkdf/

2024-09-22 16:06:56

I could really use a three-day weekend right at this moment.

2024-09-19 18:11:49

- reply

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

2024-09-19 18:09:44

- reply

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.)

2024-09-19 18:08:12

Most of cryptography research is developing a really nice mental model for what’s possible and impossible in the field, so you can avoid wasting time on dead ends. But every now and then someone kicks down a door and blows up that intuition, which is the best kind of result.