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 however
the given F doesn't have very nice avalanche property, the question of
potential improvements
naturally arises.

I found that post-processing y, the output of F, with a bit rotation of
an amount that is
variable and dependent on y can very effectively help, which in
retrospect is easily
understandable. Note that a rotation by a amount that is pseudo-random
but independent of the
value of y would not contribute to the avalanche of the function, though
it can add some
security to the function as it commonly does. (One can certainly also
use a combination of both
kinds of rotations, if considered desirable.) In an experiment F was
chosen to be a 2nd degree
permutation polynomial mod 2**n (its software implementation can be
found in e.g. my Python code
JADE-S, available in http://s13.zetaboards.com/Crypto/topic/7072208/1/).
The amount of rotation
of bits was chosen to be the number of 1-bits in the n bits of y. (Note
that this rotation is
reversible.) The following is the statistical evaluation with 1000
pseudo-randomly generated
F'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.82

M. K. Shen