Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


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

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



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

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.