From: (Bryan G. Olson; CMSC (G))
Newsgroups: sci.crypt

Subject: Re: Toward Axiomatic Fenced DES (long!)
Date: 2 Jun 1994 18:53:05 GMT
Organization: University of Maryland, Baltimore County
Lines: 16
Message-ID: <2sl9qh$>
References: <> <2sjjjg$>
X-Newsreader: TIN [version 1.2 PL2]

Bryan G. Olson; CMSC (G) ( wrote:

: THEOREM: Given n-bit strings a and b with a <> b, if P(x) is chosen
: (independently of (x,y) ) from a uniform distribution of all
: permutations of the set of n-bit strings, then the expected Hamming
: weight of P(a) xor P(b) is:

:        2**(n-1) / (2**n -1)

: (The Hamming weight of the xor is the number of different bits.)

Oops.  That's the probability a given bit has changed.  The expected
number of changed bits is n times this.

: --Bryan