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

- Everyone needs to do some work beforehand.
- Each person chooses 2
^{32}64-bit keys at random, - Each person stores these keys in a personal hash table, hashed by the secure hash function. This is their private key.
- Each person makes a file out of all their hash values,
- Each person makes that file public. This is their public key.

- Each person chooses 2
- When I want to communicate with you,
- I read your file,
- I check each of those values against my hash table (there will be about one match on average by the birthday paradox),
- If I find a match I send you the matching hash value(s),
- You look up the keys for those hash values,
- We do sanity checks, like hash the key with a different hash function (also assumed secure) and compare those hash values,
- 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^{63} keys on
average to deduce the key for our matching hash value. The
eavesdropper also sees about 2^{33} hashes that don't match,
but that doesn't help much (2^{64}-2^{33} is about
2^{64}).

2^{32} is feasible, that's 4 billion, but 2^{63} 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^{40} term files.

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

My attempts at security protocols

Hash functions and block ciphers

Designing the Dirigiped

Table of Contents