**Classes of Plateaued Rotation Symmetric Boolean Functions under Transformation of Walsh Spectra**

*Alexander Maximov*

**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$.

**Category / Keywords: **foundations / algebraic attack, algebraic immunity, Boolean functions, plateaued functions, balancedness, nonlinearity, combinatorial cryptography, Walsh transform

**Publication Info: **An extanded abstract of this full version paper will be submitted to WCC-2005

**Date: **received 13 Dec 2004

**Contact author: **movax at it lth se

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

**Version: **20041213:195729 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]