CryptoDB
Classes of Plateaued Rotation Symmetric Boolean Functions under Transformation of Walsh Spectra
Authors: |
- Alexander Maximov
|
Download: |
- URL: http://eprint.iacr.org/2004/354
- Search ePrint
- Search Google
|
Abstract: |
Construction methods of Boolean functions with cryptographically
significant properties is an important and difficult problem.
In this work we investigate the class of rotation symmetric
Boolean functions (RSBFs). These functions
are invariant under circular translation of indices and
were mainly introduced for efficient implementation purposes.
First, we derive general results on these functions. Afterwards,
we concentrate on plateaued RSBFs on odd number of variables,
which have three valued Walsh Spectra ($0, \pm \lambda$), and
can have maximum nonlinearity.
We consider both cases when the number of
variables $n$ is composite and prime.
%
When $n$ is odd and prime, we derive the constructive relation
between {\it balanced/unbalanced} plateaued RSBFs and show how
from one given such function the complete sub class can be generated.
As long as search for one plateaued RSBF is of high complexity,
our proposed manipulation technique with Walsh spectra imediately give us
the way to construct many such functions without time
consuming. Since the most important properties of a function are
determined via the values of Walsh spectra, then such transformation
technique is important to create new function with, possible, better
properties. The application of our transformation technique construct
a class of
$\left((2^{\frac{n-1}{2}}+1)/n\right)!\cdot
\left(2^{\frac{n-1}{2}}-1\right)$
balanced/unbalanced plateaued RSBFs.
%
In our practical implementation of this technique,
given one balanced PRSBF on $n=11$ variables we could
construct 185 new such functions. To find the
first function took us several days, whereas to construct new 185 functions
took us just a second. However, this technique can
be applied only when the Legendre symbol $(2/n)$ is $-1$, and
the first such $n$'s are $3, 5, 7, 11, 13, 19, 29, 37, 43, \ldots$.
|
BibTeX
@misc{eprint-2004-12317,
title={Classes of Plateaued Rotation Symmetric Boolean Functions under Transformation of Walsh Spectra},
booktitle={IACR Eprint archive},
keywords={foundations / algebraic attack, algebraic immunity, Boolean functions, plateaued functions, balancedness, nonlinearity, combinatorial cryptography, Walsh transform},
url={http://eprint.iacr.org/2004/354},
note={An extanded abstract of this full version paper will be submitted to WCC-2005 movax@it.lth.se 12765 received 13 Dec 2004},
author={Alexander Maximov},
year=2004
}