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

[Dave Farber <farber () cis upenn edu>]

> Date: Tue, 20 Feb 2001 16:50:24 -0500
> From: "Dorothy E. Denning" <denning () cs georgetown edu>
> Organization: Georgetown University
> X-Mailer: Mozilla 4.75 [en]C-C-UDP; 
> georgetownU-campus-4.7-03.08.2000  (Win98; U)
> X-Accept-Language: en
> To: farber () cis upenn edu
> Subject: Re: IP: The Key Vanishes: Scientist Outlines Unbreakable Code
>
> Dave, I made a bit/byte error in what I just sent.  The storage 
> requirements are
> even worse. The following is a corrected (I hope) version.
> Dorothy
> --------
> Dave,
>
> My understanding, based on the description Gina forwarded me from Rabin, 
> is that
> to send a message that is m bits long requires that the sender and receiver
> share (in advance) a secret key S that contains m*k random indexes, where k is
> say 210.  These indexes are used to pull bits out of the random stream that is
> transmitted from the satellite (or whatever).  Whereas the satellite bits 
> do in
> fact disappear, the key S stays around for future use. Even though the 
> satellite
> bits are the ones that are XORed into the message (the actual process is more
> complicated than with a standard stream cipher), the real key is S.
>
> Now, suppose you want to send a 10 Mb file (1.25 MB).  Suppose each index is a
> 4-byte integer.  Then for k = 210, you need a key that is 10**7 * 210 * 4 = 8
> GB.  For a 100 Mb file, the key is 80 GB.  If Alice wants to be able to
> communicate with 100 people, the storage requirements go up by another 
> factor of
> 100.  There is also the issue of how Alice and Bob exchange the secret S 
> in the
> first place (wouldn't it be easier to exchange the 10 MB message than the 
> 80 GB
> key?).  The system does not obviate the need for standard crypto -- it 
> only adds
> additional complexity (and more opportunities to introduce security weaknesses
> into the implementation).
>
> This is why I told Gina I thought the scheme was impractical, but still very
> interesting theoretically.  Of course, it is possible I misinterpreted 
> something
> and things are not so bad.
>
> Regards,
> Dorothy
>
> Dave Farber wrote:
> > 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
> >
> > For archives see: http://www.interesting-people.org/
>
> --
> Prof. Dorothy E. Denning
> Georgetown University
> http://www.cs.georgetown.edu/~denning



For archives see: http://www.interesting-people.org/