Title: Algorithms for rotation symmetric Boolean functions

Authors: Subrata Das; Satrajit Ghosh; Parthasarathi Dasgupta; Samar Sensarma

Addresses: Department of Information Technology, Academy of Technology, Aedconagar, Hooghly 712121, West Bengal, India ' Department of Computer Science, APC College, Kolkata 700131, West Bengal, India ' Management Information Systems Group, Indian Institute of Management Calcutta, Kolkata 700104, West Bengal, India ' Department of Computer Science & Engineering, University of Calcutta, Kolkata 700009, West Bengal, India

Abstract: Rotation Symmetric Boolean Functions (RSBFs) are of immense importance as building blocks of cryptosystems. This class of Boolean functions are invariant under circular translation of indices. It is known that, for n-variable RSBF functions, the associated set of all possible input n-bit strings can be divided into a number of subsets (called partitions or orbits), where every element (n-bit string) of a subset can be obtained by simply rotating the string of bits of some other element of the same subset. In this paper, for a given value of n, we propose algorithms for the generation of these partitions of all possible n-bit strings, each partition corresponding to a specific n-variable RSBF and its associated circular translations. These partitions can then be used to generate all possible n-variable RSBFs. The proposed algorithms are implemented for a maximum value of n = 41.

Keywords: algorithms; cryptography; rotation symmetric Boolean functions; RSBF; information coding; cryptosystems; partitions; n-bit strings.

DOI: 10.1504/IJICOT.2014.066109

International Journal of Information and Coding Theory, 2014 Vol.2 No.4, pp.238 - 265

Accepted: 14 Sep 2014
Published online: 24 Nov 2014 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article