Welcome to the resource topic for 2025/1779
Title:
Computing the Restricted Algebraic Immunity, and Application to Weightwise Perfectly Balanced Functions.
Authors: Luca Bonamino, Pierrick Méaux
Abstract:Algebraic Immunity (AI) 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 AI and, more specifically, on its generalization to restricted algebraic immunity, which considers annihilators constrained to specific subsets of \mathbb{F}_2^n. While the computation of AI 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 \mathbb{F}_2^n, i.e. the sets of binary vectors of fixed Hamming weight, denoted \mathsf{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 \mathsf{AI}_k distributions for WPB functions with 4, 8, and 16 variables, as well as an evaluation of \mathsf{AI}_k for various known function families.
ePrint: https://eprint.iacr.org/2025/1779
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .