Although I came up with this on my own, someone else came up with it first. See this paper (which John Kelsey pointed me to):
Davida, Desmedt, and Peralta, "A Key Distribution System Based On Any One-Way Function", Advances in Cryptology--Eurocrypt '89, Springer-Verlag, 1990
A key-exchange algorithm based on one-way hash functions and the birthday paradox. No factoring, knapsacks, or third parties involved. It is provably secure assuming you can find a one-way hash function which is secure. I'll assume the hash produces 64-bit results.
This establishes a 64-bit secret key between whoever knows the contents of those two hash tables.
An eavesdropper sees which hash value matches, but we've assumed that brute force is the easiest way to find the key that matches a given hash value. The eavesdropper must guess 263 keys on average to deduce the key for our matching hash value. The eavesdropper also sees about 233 hashes that don't match, but that doesn't help much (264-233 is about 264).
232 is feasible, that's 4 billion, but 263 is beyond anyone's ability right now. So this is feasible and it is secure. Maybe not practical, but hey, I'm doing the best I can here.
If computers get bigger and faster, then everyone upgrades to 80-bit keys and 240 term files.
The files don't have to be the same size -- the CIA could have a 244 element hash table (and have no public key at all) and isolated spies could have just 220 values and still get a 64-bit key with this scheme. (Nobody could steal the CIA's private key without a forklift.)
Or you could have 50-bit keys, keep a 230 element hash table and put only 220 of those hash values in your public file.
My attempts at security protocols
Hash functions and block ciphers
Designing the Dirigiped
Table of Contents