----- Forwarded message from Dave Farber <farber@cis.upenn.edu> -----
Date: Tue, 20 Feb 2001 14:21:14 -0500
From: Dave Farber <farber@cis.upenn.edu>
Subject: IP: Re: The Key Vanishes: Scientist Outlines Unbreakable Code
To: ip-sub-1@majordomo.pobox.com
X-Sender: farber@linc.cis.upenn.edu
X-Mailer: QUALCOMM Windows Eudora Version 5.0.2
Reply-To: farber@cis.upenn.edu
>X-Sender: larry@pop.walltech.com (Unverified)
>Date: Tue, 20 Feb 2001 10:42:26 -0800
>To: farber@cis.upenn.edu
>From: Larry Tesler <larry@nomodes.com>
>Subject: Re: IP: The Key Vanishes: Scientist Outlines Unbreakable Code
>
>>The Key Vanishes: Scientist Outlines Unbreakable Code
>>
>>By GINA KOLATA
>>
>>computer science professor at Harvard says he has found a way to send
>>coded messages that cannot be deciphered, even by an all-powerful
>>adversary with unlimited computing power. And, he says, he can prove it.
>>
>>http://www.nytimes.com/2001/02/20/science/20CODE.html
>
>Dave,
>
>I am no encryption expert. And all I know about Dr. Rabin's scheme is what
>is in the Kolata article. But I think there is a weak assumption.
>
>Before discussing the weak assumption, I'd like to point out that the
>random number stream could not be generated by a seed-based algorithm. If
>they were, whoever programmed the generator could replay the sequence at
>will. Instead, the sequence would have to be based on nuclear decay or
>something else that could not be predicted. That could be done.
>
>The article suggested that the stream could be transmitted from an Earth
>satellite, and thus be available to the sender, the receiver, and the
>would-be code breaker. The claim is that to buy the time needed to decode
>any message, the code breaker would have to have an unlimited quantity of
>computer memory to store the ultra high speed data stream that the sender
>and receiver simply use once and discard. I think not.
>
>There are two cases.
>
>Case 1. The code breaker intercepts the message in real time as it is
>transmitted from sender to receiver.
>
>For the code to be unbreakable, the data rate of the random number stream
>would have to be so high that no storage mechanism available to the code
>breaker could possibly buffer S+D seconds of the stream. S is the time it
>takes for the code breaker to decode the traditionally encrypted Start
>message that contains the agreement about which bits to select from the
>random stream and use to form the key. D is the time it takes for the code
>breaker's fast computer to catch up with the slower computers that the
>sender and receiver of the encrypted message use. The higher the ratio of
>the code breaker's computer's speed to the receiver's computer's speed,
>the smaller are N and D. The code breaker with "unlimited computing power"
>would have no problem at all.
>
>Case 2. The code breaker obtains the message some time after it is sent.
>
>The code breaker, a government agency, could use outer space as a vast
>delay line. The agency could position a few permanent relay stations
>around the orbit of Saturn, about 1 light-hour from the Sun. These
>stations would form a delay line about 6 hours in length. If they were
>capable of relaying 1500 simultaneous data streams, they could use space
>to store a full year's data stream. With at most a few hours' notice, the
>agency could access the stream that originated at any time within the past
>year.
>
>A similar ring in the orbit of Neptune (4 light-hours from the Sun) could
>store all data streams that originated between one and five years ago.
>
>For longer-term storage, space probes could be sent out of the solar
>system in several different directions, forming an ever-growing ring. If
>these probes were ion-propelled and accelerated as they receded from
>Earth, the storage capacity of the ring they formed would grow more than
>linearly with time.
>
>I admit that deploying a bevy of distant satellites would be expensive,
>and that they would have to communicate at 1500 times the speed of the
>postulated high-speed transmitter in Earth orbit. Error correction and
>other issues would create complications. But I think the Gedanken
>experiment uncovers a weakness in one assumption of Dr. Rabin's scheme, if
>I understand the scheme correctly. There likely are cheaper and more
>practical ways to exploit the weakness.
>
>Larry Tesler
>
For archives see: http://www.interesting-people.org/
----- End forwarded message -----
Tony.
-- f.a.n.finch fanf@covalent.net dot@dotat.at BAILEY: WESTERLY 5 TO 7, OCCASIONALLY GALE 8 IN NORTH. SHOWERS. MODERATE BECOMING GOOD.
This archive was generated by hypermail 2b29 : Fri Apr 27 2001 - 23:18:04 PDT