Secure key exchange with hashing and the birthday paradox

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.

1. Everyone needs to do some work beforehand.
   1. Each person chooses 2³² 64-bit keys at random,
   2. Each person stores these keys in a personal hash table, hashed by the secure hash function. This is their private key.
   3. Each person makes a file out of all their hash values,
   4. Each person makes that file public. This is their public key.
2. When I want to communicate with you,
   1. I read your file,
   2. I check each of those values against my hash table (there will be about one match on average by the birthday paradox),
   3. If I find a match I send you the matching hash value(s),
   4. You look up the keys for those hash values,
   5. We do sanity checks, like hash the key with a different hash function (also assumed secure) and compare those hash values,
   6. We choose one of the matching keys as the shared key. (If no keys match, tough, we're out of luck.)

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 2⁶³ keys on average to deduce the key for our matching hash value. The eavesdropper also sees about 2³³ hashes that don't match, but that doesn't help much (2⁶⁴-2³³ is about 2⁶⁴).

2³² is feasible, that's 4 billion, but 2⁶³ 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 2⁴⁰ term files.

The files don't have to be the same size -- the CIA could have a 2⁴⁴ element hash table (and have no public key at all) and isolated spies could have just 2²⁰ 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 2³⁰ element hash table and put only 2²⁰ of those hash values in your public file.

My attempts at security protocols
Hash functions and block ciphers
Designing the Dirigiped
Table of Contents