tallpaul writes:
At this point, this holiday season, I had an image of Merkle sitting by the tree putting an infinite number of prime numbers in an infinite number of boxes. (In the real world I've been fighting with my landlord and suddenly thought of Cantor's first description of the landlord's dilema where a landlord has an infinite number of rooms, all full, when another guest shows up and wants a room.)
:]
At this point, I suddenly had an image of Cantor sitting on the floor next to Merkle. Merkle would pack an infinite number of boxes and hand each box to Cantor who would proceed to wrap each box in an infinite number of sheets of wrapping paper.
Suddenly, I saw that my first suggested solution put all of the major work on Alice. She had to generate 10^6 prime pairs and send them all to Bob then brute force an average of (10^6)/2 attempts to discover the one pair Bob picked ot factor.
This process *might* be speeded up if Bob would, Cantor-like, help out. In other words, have Alice generate and transmit 10^3 prime pairs and have Bob do the same. This cuts transmission time by 5*(10^5), a considerable savings.
Mmm, didn't you just cut it in half (assuming simultaneous receive/transmit), saving about 10^3 time ? (I can't get through to the archives at the moment.) Anyway, it's a nice improvement to the protocol.
Then Alice and Bob each have to brute force an average of 5*(10^2) attempts to discover each others primes, for a similar savings.
However, you still need a nonpatented algorythm that lets them use the four primes to encypher their message(s) while forcing the others on the elevator to factor an average of (10^3^2)/2 products instead of 2*((10^3)/2).
This is still very far from a solution to the elevator problem as re-posed by Futplex but creates at least one way of *potetentially* shortening the prime generation and transmission time issue he was kind enough to point out.
I guess we should once again wish Roger Schlafly the best of luck in his ongoing litigation. While we're on the subject, I've just noticed an interesting protocol in Schneier, "invented by Shamir but never published", for communication over an insecure channel without a shared secret ["Shamir's Three Pass Protocol" in v.1,Sec.16.1,pp.376-377]. This protocol seems to have very appealing features, so I'm a little surprised that only the initial reference is given in Schneier. Using Shamir's proposed commutative symmetric cipher with it, I suppose it's probably slower than DH for key exchange, and progress on the discrete log problem would affect it just as much as RSA. Anyone have other references offhand, or know any other reasons this protocol isn't so useful ? -Futplex <futplex@pseudonym.com>