Rotation-Symmetric Boolean Functions – Count and Cryptographic Properties
Abstract
In 1999, Pieprzyk and Qu presented rotation symmetric (RotS) functions as components in the rounds of hashing algorithm. Later, in 2002, Cusick and St ̆anic ̆a presented further advancement in this area. This class of Boolean functions are invariant under circular translation of indices. In this paper, using Burnside’s lemma, we prove that the number of n-variable rotation symmetric Boolean functions is 2gn , where gn = 1/n∑t|nφ(t)2n/t , and φ(.) is the Eulern phi-function. Moreover, we find the number of short and long cycles of elements in Zn/2 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 found that there are exactly 8,48, and 15104, RotS bent functions on 4,6, and 8 variables respectively. Experimental results up to 10 variables show that there is no homogeneous rotation symmetric bent function with degree > 2. Further, we studied the RotS functions on 5,6,7 variables for correlation immunity and propagation characteristics and found some functions with very good cryptographic properties which were not known earlier.
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.Collections
Related items
Showing items related by title, author, creator and subject.
-
Worst and Best Irredundant Sum-of-Products Expressions
Sasao, Tsutomu; Butler, Jon T. (2011-09);ÐIn an irredundant sum-of-products expression (ISOP), each product is a prime implicant (PI) and no product can be deleted without changing the function. Among the ISOPs for some function f, a worst ISOP (WSOP) is an ISOP ... -
On the size of PLA's required to realize binary and multiple-valued functions
Bender, Edward A.; Butler, Jon T. (1989-01);While the use of programmable logic arrays in modern logic design is common, little is known about what PLA size provides reasonable coverage in typical applications. We address this question by showing upper and ... -
Rotation symmetric Boolean functions---count and cryptographic properties
Stănică, Pantelimon; Maitra, Subhamoy (2008);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 ...