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