Abstract :
[en] Algebraic immunity is a fundamental property in the security analysis of stream ciphers and Boolean functions, measuring the resistance of a function against algebraic attacks. In this work, we focus on the computation of algebraic immunity and, more specifically, on its generalization to restricted algebraic immunity, which considers
annihilators constrained to specific subsets of (F_2)^n. While the computation of algebraic immunity has been studied using methods based on Reed-Muller codes and iterative rank-based algorithms, these approaches have not been
formally adapted to the restricted setting. We address this gap by establishing the theoretical foundations required for the adaptation of these techniques and providing explicit algorithms for computing restricted algebraic immunity.
To assess the efficiency of our algorithms, we conduct practical experiments comparing the computational cost of the Reed-Muller and iterative approaches in terms of time and memory. As a case study, we analyze the algebraic immunity restricted to the slices of (F_2)^n , i.e. the sets of binary vectors of fixed Hamming weight, denoted AI_k . The
slices are of particular interest in areas of cryptography, such as side-channel analysis and stream cipher design, where the input weight may be partially predictable. We further investigate restricted algebraic immunity for Weightwise (Almost) Perfectly Balanced (W(A)PB) functions, which have been extensively studied since 2017.
Our results include an empirical analysis of AI_k distributions for WPB functions with 4, 8, and 16 variables, as well as an evaluation of AI_k for various known function families.
