Novel Approach to Degree, Balancedness, and Affine Equivalence of Boolean Functions and Construction of a Special Class of Non-Quadratic Balanced Boolean Functions

In several stream cipher designs, Boolean functions (BFs) play a crucial role as non-linear components, either serving as filtering functions or being used within the combining process. The overall strength of stream ciphers mainly depends on certain cryptographic properties of BFs, including their balancedness, non-linearity, resistance to correlation, and algebraic degrees. In this paper, we present novel findings related to the algebraic degrees of BFs, which play an important role in the design of symmetric cryptographic systems, and propose a novel algorithm to directly deduce the algebraic degree of a Boolean function (BF) from its truth table. We also explore new results concerning balanced Boolean functions, specifically characterizing them by establishing new results regarding their support. Additionally, we propose a new approach for a subclass of affine equivalent Boolean functions and discuss well-known cryptographic properties in a very simple and lucid manner using this newly introduced approach. Moreover, we propose the first algorithm in the literature to construct non-quadratic balanced Boolean functions (NQBBFs) that possess no linear structure where their derivative equals 1. Finally, we discuss the complexity of this algorithm and present a table that shows the time taken by this algorithm, after its implementation in SageMath, for the generation of Boolean functions corresponding to different values of n (i.e., number of variables).