Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs

2025/10/02 by Sarkar, Palash · 1 citation
#Cryptography and Security (cs.CR) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2510.01720

Abstract

We describe several families of efficiently implementable Boolean functions achieving provable trade-offs between resiliency, nonlinearity, and algebraic immunity. In particular, the following statement holds for each of the function families that we propose. Given integers m₀≥ 0, x₀≥ 1, and a₀≥ 1, it is possible to construct an n-variable function which has resiliency at least m₀, linear bias (which is an equivalent method of expressing nonlinearity) at most 2^-x₀ and algebraic immunity at least a₀; further, n is linear in m₀, x₀ and a₀, and the function can be implemented using O(n) 2-input gates, which is essentially optimal.

Citations

• The Nonlinear Filter Model of Stream Cipher Redivivus
• Basic Theory in Construction of Boolean Functions with Maximum Possible Annihilator Immunity

Cited by

• The Grain Family of Stream Ciphers: an Abstraction, Strengthening of Components and New Concrete Instantiations

Related

• Use of Simple Arithmetic Operations to Construct Efficiently Implementable Boolean functions Possessing High Nonlinearity and Good Resistance to Algebraic Attacks
• On Boolean Functions with Low Polynomial Degree and Higher Order Sensitivity
• Construction and Count of Boolean Functions of an Odd Number of Variables with Maximum Algebraic Immunity
• Resilient functions: Optimized, simplified, and generalized
• A remark on algebraic immunity of Boolean functions