Nonlinear Complexity of Boolean Permutations

Abstract

We introduce the concept of nonlinear complexity, where the complexity of a function is determined by the number of nonlinear building blocks required for construction. We group functions by linear equivalence, and induce a complexity hierarchy for the affine equivalent double cosets. We prove multiple invariants of double cosets over the affine general linear group, and develop a specialized double coset equivalence test. This is used to classify the 16! permutations over 4 bits into 302 equivalence classes, which have a maximal nonlinear depth of 6. In addition, we present a new complexity class defined in terms of nonlinearity.