Rotation symmetric Boolean functions---count and cryptographic properties
Loading...
Authors
Stănică, Pantelimon
Maitra, Subhamoy
Subjects
rotation symmetric Boolean functions
enumeration
correlation immunity
resiliency
algebraic degree
nonlinearity
autocorrelation
enumeration
correlation immunity
resiliency
algebraic degree
nonlinearity
autocorrelation
Advisors
Date of Issue
2008
Date
12-2-2006
Publisher
Language
Abstract
Rotation symmetric (RotS) Boolean functions have been used as components of different cryptosystems. This class of Boolean functions are invariant under circular translation of indices. Using Burnsideﾒs lemma it can be seen that the number of n-variable rotation symmetric Boolean functions is 2gn, where gn = 1 nPt|n (t) 2n t , and (.) is the Euler phi-function. In this paper, we find the number of short and long cycles of elements in Fn2 having fixed weight, under the RotS action. As a consequence we obtain the number of homogeneous RotS functions having algebraic degree w. Our results make the search space of RotS functions much reduced and we successfully analyzed important cryptographic properties of such functions by executing computer programs. We study RotS bent functions up to 10 variables and observe (experimentally) that there is no homogeneous rotation symmetric bent function having degree > 2. Further, we studied the RotS functions on 5, 6, 7 variables by computer search for correlation immunity and propagation characteristics and found some functions with very good cryptographic properties which were not known earlier.
Type
Article
Description
The article of record as published may be located at http://dx.doi.org/10.1.1.137.6388
Series/Report No
Department
Applied Mathematics
Organization
Naval Postgraduate School (U.S.)
Identifiers
NPS Report Number
Sponsors
Funding
Format
Citation
Discrete Appl. Math. / Volume 156, Issue 10, 1567-1580, #47.
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.