Path: cactus.org!milano!cs.utexas.edu!usc!rpi!news-server.csri.toronto.edu!
+     bonnie.concordia.ca!clyde.concordia.ca!altitude!elevia!alain
From: alain@elevia.UUCP (W.A.Simon)
Newsgroups: sci.crypt

Subject: Re: eating pretzels
Message-ID: <1991Jul21.133354.9428@elevia.UUCP>
Date: 21 Jul 91 13:33:54 GMT
References: <1991Jul15.110725.8635@elevia.UUCP> <220@armltd.uucp>
Organization: The Electronic Path - Global Village
Lines: 58

In <220@armltd.uucp> dseal@armltd.co.uk (David Seal) writes:
> In article <1991Jul15.110725.8635@elevia.UUCP> alain@elevia.UUCP (W.A.Simon)
>writes:
>>In <218@armltd.uucp> dseal@armltd.co.uk (David Seal) writes:
>>>In article <1991Jul2.105754.11804@elevia.UUCP> alain@elevia.UUCP (W.A.Simon)
>writes:
>>>> [ ... ]
>>> [ ... generic data-dependent XOR... ]
>>	I am not quite certain what you mean by data dependant and
>>	how it is relevant to this discourse.
> I'd have thought that it was pretty clear. A data-dependent XOR is one where
> the value that you XOR with depends on the data being encrypted. A
> data-independent XOR is one where the value that you XOR with does not
> depend on this data.

	In a real life cryptographic sesssion, why would anyone use
	anything else than a fully random key to XOR the plaintext
	with?  This qualifies as data independant.  My choice of
	data dependant XOR keys is for the purpose of analysis only.

> Now for the reason that it is relevant to this discourse:
>   Data-independent XORs are not a subset of shuffles. Proof: Consider the
>     data-independent XOR of XORing all bits with 1. This swaps the number of
>     0's and 1's in the stream, which a shuffle cannot possibly do in the
>     general case.

	OK, so it would seem that a XOR can do more...  but that was the
	conclusion all along anyway.

>   Shuffles are not a subset of data-independent XORs. Proof: look at the
>     simple "swap two bits" example I gave above. The XOR value would have to
>     depend on the data.

	For any shuffle you care to effect on a string, there is a XOR
	that will achieve the same result.  I don't see that you have
	proven otherwise.  I am not proposing to use specialy picked
	key material in order to make a XOR behave like a shuffle, I am
	just saying there exists a XOR that will do what the shuffle
	does.

>   Data-independent XORs are known to be easy to decrypt if the text is
>     sufficiently longer than the key. (If the key is longer than the text,
>     we can have a one-way pad, which is provably secure.) If we could

	Our premises were, all along, that infinite length one-time pads
	are being used...

>     conclude that shuffles, and hence braided streams, were weaker than
>     data-independent XORs, we would be able to draw conclusions about their
>     cryptographic strength. But we cannot conclude this.

	I have shown that (to use your vocable) there is a data dependant
	XOR that will achieve the same result as the braid or the shuffle.
	We can safely assume that a data independant XOR will be stronger.
	In my own choice of vocabulary, the notion of data dependancy came
	out as "constrained key space".

> [ ... ]
-- 
William "Alain" Simon                                         alain@elevia.UUCP