You are looking at a specific version 20041213:195729 of this paper. See the latest version.

Paper 2004/354

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

Metadata
Available format(s)
PS
Category
Foundations
Publication info
Published elsewhere. An extanded abstract of this full version paper will be submitted to WCC-2005
Keywords
algebraic attackalgebraic immunityBoolean functionsplateaued functionsbalancednessnonlinearitycombinatorial cryptographyWalsh transform
Contact author(s)
movax @ it lth se
History
2004-12-13: received
Short URL
https://ia.cr/2004/354
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.