International Association for Cryptologic Research

International Association
for Cryptologic Research

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
}