```Date: Dec 12, 2013 3:27 PM
Author: Mok-Kong Shen
Subject: Improving avalanche property of functions with bit rotations

If a n-bit bijective function F is used in an encryption algorithm to transform a value x to y,i.e. y = F(x), it is commonly desirable that its avalanche property be superior. That is,changing one single bit of x will produce lots of changes of bits of y. In case howeverthe given F doesn't have very nice avalanche property, the question of potential improvementsnaturally arises.I found that post-processing y, the output of F, with a bit rotation of an amount that isvariable and dependent on y can very effectively help, which in retrospect is easilyunderstandable. Note that a rotation by a amount that is pseudo-random but independent of thevalue of y would not contribute to the avalanche of the function, though it can add somesecurity to the function as it commonly does. (One can certainly also use a combination of bothkinds of rotations, if considered desirable.) In an experiment F was chosen to be a 2nd degreepermutation polynomial mod 2**n (its software implementation can be found in e.g. my Python codeJADE-S, available in http://s13.zetaboards.com/Crypto/topic/7072208/1/). The amount of rotationof bits was chosen to be the number of 1-bits in the n bits of y. (Note that this rotation isreversible.) The following is the statistical evaluation with 1000 pseudo-randomly generatedF's:    n    post-proc.    mean avalanche   standard deviation    64       no            16.73              0.97            yes            29.93              1.30   128       no            32.75              1.35            yes            60.71              1.67   256       no            64.79              1.96            yes           122.81              2.24   512       no           128.71              2.66            yes           248.44              2.82M. K. Shen
```