On the algebraic immunity of weightwise perfectly balanced functions

Agnese Gini; Pierrick Méaux

Paper 2023/495

On the algebraic immunity of weightwise perfectly balanced functions

Agnese Gini

, University of Luxembourg

Pierrick Méaux

, University of Luxembourg

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$.

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: BooleanFunctions Weightwise perfectly balancedness Algebraic 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}
}