From: tallpaul@pipeline.com (tallpaul)
Date: Sat, 16 Dec 1995 19:32:42 +0800
To: cypherpunks@toad.com
Subject: The Elevator Problem & Groucho's Duck
Message-ID: <199512160537.AAA23233@pipe6.nyc.pipeline.com>
MIME-Version: 1.0
Content-Type: text/plain


On Dec 14, 1995 04:44:12, 'futplex@pseudonym.com (Futplex)' was kind enough
to respond to my post on the elevator problem. 
 
I thought his response was insightful and appropriate but that the
description of the problem had changed a bit since the problem was first
posed. 
 
Thus this post. 
 
I've been thinking of the old game show hosted by Groucho Marx. You would
"say the secret word and win $100." 
 
Getting the $100 was easy. The duck would drop down on a string with the
money in its beak and you'd just pluck it out. Saying the secret word was
also an easy problem to hack. You could just read the dictionary. Of course
this hack didn't work in real time because the show only lasted 30 minutes,
Groucho did most of the talking, and you had to say the secret word in
normal conversation. All of this rather "limited the bandwidth." 
 
The elevator problem remains somewhat undefined as a problem. Several
parameters are boundaries within which the basic problem must be solved.
Two parameters are the length of time Alice and Bob will spend coupled
against the desired level of security. 
 
Highly specific solutions are effectively impossible until these parameters
are defined (or at least approximated). 
 
However ... 
 
My original solution involved a variation of Merkle's non-patented puzzles.
Futplex stated, correctly, that this took a goodly amount of time to
generate and transmit the puzzles and the security was "not so hot." 
 
My mind still returns to Merkle and the idea of solving the original
elevator problem that could be geometric for Alice and Bob while being
exponential for the other people on the elevator. The more I tried to focus
on this aspect of the problem the more I just repeated the problem in my
own mind. 
 
I felt that I was trapped in a "maze of twisty little passages, all the
same." 
 
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. 
 
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 now feel that I am only "trapped in a maze of twisty little passages, all
different." 
 
Comment, Futplex? 
 
--tallpaul