Path: cactus.org!milano!radar!cs.utexas.edu!samsung!emory!ox.com!yale.edu!
+     cmcl2!kramden.acf.nyu.edu!brnstnd
From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein)
Newsgroups: sci.crypt

Subject: Another proof that Simon's system doesn't work
Message-ID: <20527.Jun2419.22.0691@kramden.acf.nyu.edu>
Date: 24 Jun 91 19:22:06 GMT
Organization: IR
Lines: 27

The receiver starts knowing n bits of key. When it receives the next
ciphertext bit, it gobbles up one bit of key to figure out what the
ciphertext means. It gets back one bit of key if the gobbled bit
referred to the ``key management'' stream. It doesn't get back any bits
of key if the gobbled bit referred to the plaintext stream.

To put it differently, the receiver loses a bit of key for each bit of
plaintext transmitted. More precisely, the end of the key stream which
has been sent to the receiver, minus the end of the key stream used so
far by the receiver, decreases by 1 for each bit of plaintext
transmitted.

According to Simon's explanation, the key stream is infinite. Therefore
the receiver loses at most n - 1 bits of key; i.e., at most n - 1 bits of
plaintext are transmitted. Hence all but n - 1 of the gobbled bits refer
to the ``key management'' stream; i.e., the key is 0 for infinitely many
values and 1 for n - 1 values, or vice versa. In either case, the key
has probability 0 of coming from a uniform distribution, by the strong
law of large numbers.

So ``Braided Stream Multiplexing'' will successfully process an infinite
stream exactly 0 times. Ever. Or so we expect. And even if a miracle
occurs and someone, someday, somewhere, sees Simon's stupid system
somehow successfully satisfy his spec, at most n - 1 bits of plaintext
are transmitted and any remaining plaintext is left hanging forever.

---Dan