Welcome to the resource topic for 2023/495
Title:
On the algebraic immunity of weightwise perfectly balanced functions
Authors: Agnese Gini, Pierrick Méaux
Abstract:In this article we study the Algebraic Immunity (AI) of Weightwise Perfectly Balanced (WPB) functions.
After showing a lower bound on the AI of two classes of WPB functions from the previous literature, we prove that the minimal AI of a WPB n-variables function is constant, equal to 2 for n\ge 4 .
Then, we compute the distribution of the AI of WPB function in 4 variables, and estimate the one in 8 and 16 variables.
For these values of n we observe that a large majority of WPB functions have optimal AI, and that we could not obtain an AI-2 WPB function by sampling at random.
Finally, we address the problem of constructing WPB functions with bounded algebraic immunity, exploiting a construction from 2022 by Gini and Méaux. In particular, we present a method to generate multiple WPB functions with minimal AI, and we prove that the WPB functions with high nonlinearity exhibited by Gini and Méaux also have minimal AI. We conclude with a construction giving WPB functions with lower bounded AI, and give as example a family with all elements with AI at least n/2-\log(n)+1.
ePrint: https://eprint.iacr.org/2023/495
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 .