From: utzoo!decvax!yale-com!leichter
Newsgroups: net.math
Title: Re: random numbers
Article-I.D.: yale-com.1396
Posted: Sat Apr 23 14:03:12 1983
Received: Sun Apr 24 07:37:53 1983
References: hou5e.405

In answer to Mark Terribile:  Re knapsack systems, see my other submission to
this newsgroup a couple of minutes ago.  Re:  Factoring large numbers:  This
has nothing to do with the knapsack system.  As a separate problem, though,
progress is being made, although all known algorithms are still super-polyno-
mail - although they are sub-exponential.  (Current best is something like
exp(sqrt(log log n)) or some crazy thing like that.)  My personal feeling is
that factoring MAY be very hard, but we really don't have much good reason
to believe it at this point.  (The strong argument FOR hardness has always been
that hundreds of years of effort by the best mathematicians hadn't cracked th
\\\the problem.  Unfortunately, the efforts had as a goal a deterministic
factoring method for all numbers.  The notion of probablistic algorithms is only
a couple of years old, and thus we have almost no evidence that there is not a
fast probablistic algorithm.  Note that the Solovay-Strassen probablistic prima-
lity tester would have been perfectly understandable to Fermat - but it wasn't
though of until very recently.  Also note that, inspired by the probablistic
algorithms, deterministic algorithms have now been devised.)

The reason factoring is interesting, of course, is that the other major public-
key cryptosystem, RSA, depends on its being hard.  It turns out that there is
an attack on RSA - and, in fact, on ALL public-key systems - that has nothing
to do with factoring.  It's a bit long to go into here, but the basic argument
goes like this:  Think about, say, RSA.  Suppose I had some way to read just
the bottom bit of an encrypted message.  Could I do anything?  In fact, one
can show that the ability to determine the bottom bit in polynomial time makes
it possible to read the whole message in polynomial time.  (There is a clever
trick that lets you essentially "shift the message right one bit" once you know
the bottom bit.)  Now how do I read the bottom bit?  I - the interceptor - don't
instead, I trick you (the recipient) into reading it for me.  The particular
way in which I trick you depends on the protocol we use on our network, and it
MAY be possible to come up with a safe protocol - but no one knows how, at
the moment.  Here is an example of an unsafe protocol:  In response to a yes
or no question, send (the encryption of) an even number for yes, of an odd
number for no.  (Looks innocent, no?)  I wait until you send me a message
asking if I want to join you for pizza.  I send you the message I intercepted.
You decrypt, and check the bottom bit.  If it's 0, you think I said yes and
go to the pizza place; otherwise, you don't go.  All I have to do is watch
what you do...

The reference for this work is:  "Why and How to Establish a Private Code on
a Public Network", by Goldwasser, Micali, and Tong, Proceedings of the 23rd
FOCS, pg 134-144.  Warning:  It's a pretty technical article, and slow going.
							-- Jerry
						decvax!yale-comix!leichter
							leichter@yale