Paper 2023/495
On the algebraic immunity of weightwise perfectly balanced functions
, University of Luxembourg, University of LuxembourgAbstract
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$.
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- Published elsewhere. Minor revision. LATINCRYPT2023
- DOI
- 10.1007/978-3-031-44469-2_1
- Keywords
- BooleanFunctionsWeightwise perfectly balancednessAlgebraic immunity
- Contact author(s)
-
agnese gini @ uni lu
pierrick meaux @ uni lu - History
- 2023-10-10: revised
- 2023-04-05: received
- See all versions
- Short URL
- https://ia.cr/2023/495
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/495,
author = {Agnese Gini and Pierrick Méaux},
title = {On the algebraic immunity of weightwise perfectly balanced functions},
howpublished = {Cryptology {ePrint} Archive, Paper 2023/495},
year = {2023},
doi = {10.1007/978-3-031-44469-2_1},
url = {https://eprint.iacr.org/2023/495}
}
