The Math Forum

Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Math Forum » Discussions » sci.math.* » sci.math.num-analysis

Topic: Improving avalanche property of functions with bit rotations
Replies: 0  

Advanced Search

Back to Topic List Back to Topic List  
Mok-Kong Shen

Posts: 601
Registered: 12/8/04
Improving avalanche property of functions with bit rotations
Posted: Dec 12, 2013 3:27 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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
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

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

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2017. All Rights Reserved.