IP: Re: The Key Vanishes: Scientist Outlines Unbreakable Code

[Dave Farber <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/