From: futplex@pseudonym.com (Futplex)
Date: Mon, 18 Dec 1995 16:47:29 +0800
To: cypherpunks@toad.com (Cypherpunks Mailing List)
Subject: Re: The Elevator Problem & Groucho's Duck
In-Reply-To: <199512160537.AAA23233@pipe6.nyc.pipeline.com>
Message-ID: <199512180803.DAA01695@opine.cs.umass.edu>
MIME-Version: 1.0
Content-Type: text/plain


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>