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

We describe several families of efficiently implementable Boolean functions achieving provable trade-offs between resiliency, nonlinearity, and algebraic immunity. In concrete terms, the following result 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)$ gates.