Path: cactus.org!milano!cs.utexas.edu!usc!elroy.jpl.nasa.gov!swrinde!zaphod.
+     mps.ohio-state.edu!rpi!batcomputer!cornell!wayner
From: wayner@CS.Cornell.EDU (Peter Wayner)
Newsgroups: sci.crypt

Subject: Re: Braided streams (The Leichter Side)
Message-ID: <1991Jun24.143612.6277@cs.cornell.edu>
Date: 24 Jun 91 14:36:12 GMT
References: <1991Jun23.042445.9676@elevia.UUCP> <25633@well.sf.ca.us>
Sender: news@cs.cornell.edu (USENET news user)
Organization: Cornell Univ. CS Dept, Ithaca NY 14853
Lines: 20
Nntp-Posting-Host: kama.cs.cornell.edu


Hey, I just remembered something with regard to Braided streams
and known plaintext attacks. Let's say that you know that 
some string of bits, {b1,b2,b3...bn} which has been braided into
the ciphertext {c1,c2,...cm}. The goal is to retrieve the key, which
in this case is all the of the bits in the ci's that aren't derived
from the bi's. 

There is a UNIX command called "diff" which will display the
line-by-line differences between two text files. It will take two text
files, A and B, and figure out what lines have been inserted/deleted
in A to make B. The algorithm is pretty cool and, if I remember
correctly, runs in a reasonably polynomial time. I'll check on it. 

-Peter

-- 
Peter Wayner   Department of Computer Science Cornell Univ. Ithaca, NY 14850
EMail:wayner@cs.cornell.edu    Office: 607-255-9202 or 255-1008
Home: 116 Oak Ave, Ithaca, NY 14850  Phone: 607-277-6678