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