Construction and enumeration of correlation immune rotation symmetric Boolean functions

Boolean functions that remain unchanged under the action of cyclic group are referred to as rotation symmetric Boolean functions (RSBFs). Determining the exact count of first order correlation immune RSBFs (1-CI RSBFs) and first order correlation immune symmetric Boolean functions (1-CI SBFs) are challenging open problems in the field of cryptography. The main objective of this study is to analyze the structure of 1-CI RSBFs and to derive an explicit formula for their enumeration. We demonstrate that the construction and counting of this class of functions is equivalent to finding all the 2-partitions of a specific multiset with equal sums. Subsequently, we derive an explicit formula for counting the number of 1-CI RSBFs using multiset partition theory. Symmetric Boolean functions are the special cases of RSBFs. By applying certain conditions to the counting results of 1-CI RSBFs, we also establish an explicit formula for counting first order correlation immune symmetric Boolean functions (1-CI SBFs). In addition, we also propose a systematic counting procedure for enumerating p -variable 1-resilient RSBFs.