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

arXiv:2510.01720 · cs.CR · Submitted 2025-10-02 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: We're looking at the paper: "Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs".

Elias: Here's the gist of the paper. We describe several families of efficiently implementable Boolean functions achieving provable trade-offs between resiliency, nonlinearity, and algebraic immunity This paper provides the first general answers to the challenge of obtaining constructions of infinite families of Boolean functions with provable values or bounds on resiliency, nonlinearity, and algebraic immunity such that the functions can be efficiently implemented Problem Statement and Core Result The central challenge addressed is obtaining constructions of infinite families of Boolean functions with provable values or bounds on resiliency, nonlinearity, and algebraic immunity such that the functions can be efficiently implemented The main result states that given integers m0 ≥ 0, x0 ≥ 1 and a0 ≥ 1, it is possible to construct an n-variable function which has resiliency at least m0, linear bias at most 2−x0 and algebraic immunity at least a0 Furthermore, n is linear in max(m0, x0, a0), and the function can be implemented using O(n) 2-input gates.

Nadia: This construction is asymptotically optimal because any function which is at least m0-resilient, has linear bias at most 2−x0, and algebraic immunity at least a0 must require Ω(max(m0, x0, a0)) 2-input gates.

Elias: Construction Families for Resiliency Enhancement The paper presents several methods to construct functions with desired properties, including simple extensions and more complex iterated constructions The first class of functions is obtained by extending a special class of bent functions by simply adding a number of new variables.

Nadia: This construction shows the strong result holds for this class.

Paper summary: Nadia: So we're looking at this paper, "Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs." It seems like the main thing they're tackling is finding a way to build families of Boolean functions where you can prove limits on three different security properties—resiliency, nonlinearity, and algebraic immunity—while also making sure those functions don't take too many gates to actually build.

Elias: Right, so it addresses that tough challenge: getting infinite families of these functions that have provable values or bounds on those three properties, and they must be efficiently implementable. That's the core problem they set out to solve, as you can see from the introduction > page two of THIS PAPER Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs <ref:2510.01720#pg1,Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity>.

Priya: I'm curious about what "efficiently implementable" means in this context. Does that mean something like a low gate count, or is it about the size of the function itself? We need to know if this efficiency is practical for real cryptographic systems > page two of THIS PAPER Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs <ref:2510.01720#pg1,Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity>.

Nadia: It specifically measures efficiency by the number of two-input gates required, and they claim that their constructions use O(n) two-input gates, which is essentially optimal for any function with those properties > page one of THIS PAPER Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs <ref:2510.01720#pg1,Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity>.

Elias: That's the big claim: they can construct an n-variable function that has resiliency at least m0, linear bias at most two to xzero and algebraic immunity at least a0 > page one of THIS PAPER Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs <ref:2510.01720#pg1,Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity>.

Priya: But the paper also says that n itself grows linearly with the maximum of those three parameters: m0, xzero and a0 > page one of THIS PAPER Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs <ref:2510.01720#pg1,Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity>. That means to get better security on all fronts, you just need more variables > page one of THIS PAPER Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs <ref:2510.01720#pg1,Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity>.

Nadia: It seems like they're giving us a construction blueprint for balancing these competing security needs, which is what the title suggests about trade-offs > page two of THIS PAPER Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs <ref:2510.01720#pg1,Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity>.

Paper summary: Elias: They describe several ways to build these functions, starting with extending a special class of bent functions by just adding new variables > page three of THIS PAPER Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs <ref:2510.01720#pg3>.

Priya: Are those extensions the only way, or are there more complex ways they build these families? I'm hoping to see if there are methods beyond just adding variables > page three of THIS PAPER Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs <ref:2510.01720#pg3>.

Nadia: They describe another class where you take a five-variable, one-resilient function and then add more new variables > page three of THIS PAPER Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs <ref:2510.01720#pg3>. That's a different approach to building the family > page three of THIS PAPER Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs <ref:2510.01720#pg3>.

Elias: And they mention two more classes that aren't just about adding variables to bent functions, which brings back an idea from a prior paper seventeen > page three of THIS PAPER Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs. That shows they're looking at different structural ideas > page three of THIS PAPER Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs <ref:2510.01720#pg3>.

Priya: Okay, so we have these different ways to construct the functions. I wonder how these constructions perform when you look at specific scenarios, like for balanced or one-resilient functions > page three of THIS PAPER Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs <ref:2510.01720#pg3>.

Nadia: They compare their findings against previous work on balanced, or zero-resilient, functions and one-resilient functions > page three of THIS PAPER Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs <ref:2510.01720#pg3>.

Elias: For balanced functions, their constructions in corollary one achieve a linear bias that's almost optimal at two to minus n minus one over two, and an algebraic immunity lower bound of alpha greater than or equal to n minus one over four > page three of THIS PAPER Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs <ref:2510.01720#pg3>.

Priya: Almost optimal linear bias sounds good for practical use, but what does that mean in terms of the actual security level they're giving us? Does that lower bound on algebraic immunity translate to anything useful for privacy concerns? > page three of THIS PAPER Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs <ref:2510.01720#pg3>.

Paper summary: Nadia: For even n, the functions constructed in corollary two get almost optimal linear bias at two to minus n minus two over two and an algebraic immunity at least alpha greater than or equal to n minus two over four > page three of THIS PAPER Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs <ref:2510.01720#pg3>. That's a more specific result for even numbers > page three of THIS PAPER Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs <ref:2510.01720#pg3>.

Elias: They also have an iterated construction where they repeatedly combine functions using the step function, which means if you start with m resilient and h resilient functions, you get a new function that's m plus two t resilient > page three of THIS PAPER Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs <ref:2510.01720#pg3>.

Priya: Iterated constructions sound powerful, but I need to understand the trade-off there. How does the linear bias change when you iterate like that? > page three of THIS PAPER Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs <ref:2510.01720#pg3>.

Nadia: Theorem eight gives us specific constructions for this iterated function based on whether a number like n minus three t minus one is odd or even, yielding resiliency of two to t resilient or two to t plus one resilient > page three of THIS PAPER Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs <ref:2510.01720#pg3>. And the linear bias is two to minus n minus t over two > page three of THIS PAPER Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs <ref:2510.01720#pg3>.

Elias: The provable trade-off bounds summarized in theorem nine show that for any m0, xzero and a0, you can construct an n variable function with resiliency m0, linear bias at most two to minus xzero over two, and algebraic immunity at least a0 > page three of THIS PAPER Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs <ref:2510.01720#pg3>.

Priya: And the minimum number of gates needed for implementation is given in theorem ten as at least m0 plus one, two times xzero and two times a0 minus one minus one > page three of THIS PAPER Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs <ref:2510.01720#pg3>. So the gate count scales directly with the required security parameters > page three of THIS PAPER Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs <ref:2510.01720#pg3>.

Nadia: That means any function hitting those targets needs at least max of m0 plus one, two times xzero and two times a0 minus one minus one gates to build > page three of THIS PAPER Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs <ref:2510.01720#pg3>. That’s the efficiency constraint tied directly to the security requirements.

Paper summary: Elias: The paper concludes that any function meeting those bounds needs at least max of m0 plus one, two times xzero and two times a0 minus one minus one gates to implement > page three of THIS PAPER Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs <ref:2510.01720#pg3>. It's asymptotically optimal because any function meeting those requirements must need at least that many gates > page one of THIS PAPER Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs <ref:2510.01720#pg1,Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity>.

Priya: So, what does this mean for someone building a secure chip or a cryptographic system? It gives them concrete trade-offs they can calculate upfront between the desired level of resiliency and the required gate count > page three of THIS PAPER Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs <ref:2510.01720#pg3>.

Nadia: Exactly. It shows you that you can't just chase perfect security on all three fronts if you want an efficient design, and this paper gives a roadmap for how to navigate those competing demands > page three of THIS PAPER Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs <ref:2510.01720#pg3>.

Elias: The authors say that they've provided the first general answers to the challenge of getting these constructions, which is what makes this paper important for the field > page two of THIS PAPER Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs <ref:2510.01720#pg1,Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity>.

Priya: It’s interesting that they focus on provable bounds rather than just empirical results, because for security proofs, that certainty is what matters most > page two of THIS PAPER Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs <ref:2510.01720#pg1,Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity>.

Nadia: So, to wrap up this paper on "Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs," they give us tools to design functions that are provably secure against certain attacks while keeping the physical implementation cost predictable > page one of THIS PAPER Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs <ref:2510.01720#pg1,Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity>.

Elias: It provides a concrete construction for achieving specific levels of resiliency, linear bias, and algebraic immunity within an efficient gate count bound > page two of THIS PAPER Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs <ref:2510.01720#pg1,Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity>. This is the first general answer to that trade-off challenge they set out to solve

Conclusion: Nadia: So we’ve been digging into this paper, "Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs," and the core idea is finding ways to build functions that are provably secure against three different threats—resiliency, nonlinearity, and algebraic immunity—while keeping the physical implementation cost low.

Elias: It’s about getting a general answer to that challenge, trying to show you how you can construct these families of functions with guaranteed bounds on those security properties while making sure they only take an amount of gates proportional to the required security numbers.

Priya: The authors are focused on these provable trade-offs, which is important because we need certainty about what the data actually shows before we trust any claimed result about a system's security level.

Nadia: They’re not just showing some specific functions; they’re giving us methods—like extending bent functions or using iterated constructions—to build these families efficiently.

Elias: The main result is that you can construct an n-variable function where the resiliency is at least m zero, the linear bias is at most two to x zero, and the algebraic immunity is at least a zero.

Priya: But they also say that for this to work well, the number of variables n has to grow linearly with how big those three security parameters are. So better security on all fronts means you need more variables.

Nadia: And they give us concrete bounds on the gate count needed for implementation, showing that it’s at least max of m zero plus one, two times x zero, and two times a zero minus one minus one gates.

Elias: That gate count bound is what makes this work; it shows that any function hitting those security targets has to cost at least that much hardware to build.

Priya: So for someone building a secure chip or a cryptographic system, this means you can calculate upfront exactly how much processing power you need versus the security level you want.

Nadia: Exactly. It gives you a roadmap for balancing these competing demands, showing that you can’t just chase perfect security on all three fronts if you want an efficient design.

Elias: It provides the first general answer to that trade-off challenge they set out to solve, so we need to keep looking at how these constructions scale and what limitations they have.

Indian Statistical Institute

cs.CR

Submitted: 2025-10-02

Updated: 2026-11-11

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 90/100

The gist: We describe several families of efficiently implementable Boolean functions achieving provable trade-offs between resiliency, nonlinearity…

Key concepts

Resiliency
This property measures how resistant a Boolean function is to being approximated by low-degree polynomials. A higher resiliency means the function is harder to approximate using simple algebraic expressions, which relates to its nonlinearity.
Linear Bias (LB)
Linear bias quantifies how close a Boolean function's output distribution is to being purely random. A lower linear bias (closer to 2^-n/2) indicates that the function is more complex and less predictable by simple linear methods.
Algebraic Immunity
This measures the complexity of the algebraic structure of a Boolean function. High algebraic immunity means the function cannot be easily represented or simplified using low-degree polynomial equations, making it robust against certain types of algebraic attacks.

Terminology

Summary

We describe several families of efficiently implementable Boolean functions achieving provable trade-offs between resiliency, nonlinearity, and algebraic immunity This paper provides the first general answers to the challenge of obtaining constructions of infinite families of Boolean functions with provable values or bounds on resiliency, nonlinearity, and algebraic immunity such that the functions can be efficiently implemented

Problem Statement and Core Result

The central challenge addressed is obtaining constructions of infinite families of Boolean functions with provable values or bounds on resiliency, nonlinearity, and algebraic immunity such that the functions can be efficiently implemented The main result states that given integers m0 ≥ 0, x0 ≥ 1 and a0 ≥ 1, it is possible to construct an n-variable function which has resiliency at least m0, linear bias at most 2−x0 and algebraic immunity at least a0 Furthermore, n is linear in max(m0, x0, a0), and the function can be implemented using O(n) 2-input gates. This construction is asymptotically optimal because any function which is at least m0-resilient, has linear bias at most 2−x0, and algebraic immunity at least a0 must require Ω(max(m0, x0, a0)) 2-input gates. p. 1

Where the paper says it

Theorem (informal): Given integers m0 ≥ 0, x0 ≥ 1 and a0 ≥ 1, it is possible to construct an n-variable function which has resiliency at least m0, linear bias at most 2−x0 and algebraic immunity at least a0, where n is linear in max(m0, x0, a0), and the function can be implemented using O(n) 2-input gates, which is asymptotically optimal in the sense that any function which is at least m0-resilient, has linear bias at most 2−x0 , and algebraic immunity at least a0 must require Ω(max(m0, x0, a0)) 2-input gates. Our construction leverages a recent result from [7] which showed how to construct a special class of bent functions with provable lower bound on algebraic immunity.

Construction Families for Resiliency Enhancement

The paper presents several methods to construct functions with desired properties, including simple extensions and more complex iterated constructions

** The first class of functions is obtained by extending a special class of bent functions by simply adding a number of new variables. This construction shows the strong result holds for this class. p. 1

Where the paper says it

The first class simply adds a number of new variables, while the second class adds a 5-variable, 1-resilient function and then adds a number of new variables. We show that the above mentioned strong result holds for both of these classes.

4 **

** The second class adds a 5-variable, 1-resilient function and then adds a number of new variables. This construction also satisfies the strong result. p. 1

Where the paper says it

Instead of nonlinearity, we describe our results in terms of the equivalent notion of linear bias. We describe several infinite families of Boolean functions for which the following strong result holds.

4 **

** Two more classes of functions are described which are not obtained by just adding new variables to bent functions, resurrecting an idea from [17]. These constructions also satisfy the strong result. p. 1

Where the paper says it

Instead of nonlinearity, we describe our results in terms of the equivalent notion of linear bias. We describe several infinite families of Boolean functions for which the following strong result holds.

4 **

Trade-offs for Balanced and 1-Resilient Functions

The paper compares its findings against previous work concerning balanced (i.e., 0-resilient) functions and 1-resilient functions

** For balanced functions, the constructions in Corollary 1 achieve almost optimal linear bias of 2−(n−1)/2 and a lower bound of α ≥ (n − 1)/4 on algebraic immunity, implemented using O(n) gates. 8 **

** For even n, the functions constructed in Corollary 2 achieve almost optimal linear bias equal to 2−(n−2)/2 and algebraic immunity at least α ≥ (n − 2)/4, implemented using O(n) gates. 8 **

Iterated Construction for Advanced Properties

Construction 3 describes an iterated construction where functions are repeatedly combined using the Step function

** If g and h are m-resilient, then f(t) is (m + 2t)-resilient, and LB(f(t)) = 2−t·LB(f). 13 **

** Theorem 8 provides specific constructions for the function f(t) based on whether n − 3t − 1 is odd or even, yielding resiliency of (2t-resilient) or (2t+1)-resilient with linear bias equal to 2−(n-t-2)/2. 13 **

Provable Trade-Off Bounds

Theorem 9 summarizes the provable trade-offs achievable by the constructions, stating that for given m0, x0, and a0, an n-variable function with resiliency order m0, linear bias at most 2−x0 and algebraic immunity at least a0 can be constructed if n is sufficiently large relative to these parameters The minimum number of gates required for implementation is given by Theorem 10, which states that any such function requires at least max(m0 + 1, 2x0, 2a0 − 1) − 1 gates. Table 1 illustrates how the trade-offs achieved by the various constructions differ. p. 0

Where the paper says it

Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs Palash Sarkar Indian Statistical Institute, 203, B. Road, Kolkata, India 700108 Email: palash@isical.

Conclusion and Future Directions

The paper concludes that no previous work addresses this trade-off question in the same generality, and its constructions are simple and efficient The work suggests promising directions for future research, such as obtaining constructions that achieve better provable trade-offs between resiliency, linear bias and algebraic immunity.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Automated construction of Boolean functions with provable trade-offs: The system can construct an n-variable function with resiliency at least m0, linear bias at most 2 minus x0, and algebraic immunity at least a0, where n is linear in max(m0, x0, a0), and the function can be implemented using O(n) 2-input gates.

  2. Optimal gate count determination: The system can determine the minimum number of 2-input gates required for implementation based on the target resiliency order m0, linear bias constraint x0, and algebraic immunity requirement a0, as stated in Theorem 10.

  3. Trade-off curve mapping: The system can map desired targets (m0, x0, a0) to specific construction methods by selecting the appropriate case from Theorem 9 to achieve the required properties with minimal variables n.

Abstract

We describe new families of efficiently implementable Boolean functions achieving provable trade-offs between resiliency, nonlinearity, and algebraic immunity. Compared to one direction of research on balanced and 1-resilient functions with optimal algebraic immunity, the new functions provide lower algebraic immunity, but much lower -- in fact, almost optimal -- linear bias and importantly are much more efficient to implement. Compared to another direction of research based on constructions using direct sum, the new functions while achieving similar efficiency, has less number of variables for the same order of resiliency, same lower bound on algebraic immunity, and similar nonlinearity.

Related papers