title: On Various Nonlinearity Measures for Boolean Functions.
abstract: A necessary condition for the security of cryptographic functions is to be "sufficiently distant" from linear, and cryptographers have proposed several measures for this distance. In this paper, we show that six common measures,nonlinearity, algebraic degree, annihilator immunity, algebraic thickness, normality, andmultiplicative complexity, are incomparable in the sense that for each pair of measures, μ1, μ2, there exist functionsf1,f2withf1being more nonlinear thanf2according to μ1, but less nonlinear according to μ2. We also present new connections between two of these measures. Additionally, we give a lower bound on the multiplicative complexity of collision-free functions.
authors.affiliation: Department of Mathematics and Computer Science, University of Southern Denmark. Partially supported by the Danish Council for Independent Research, Natural Sciences. Part of this work was done while visiting the University of Waterloo.
authors.forename: Joan
authors.initials: J
authors.lastname: Boyar
authors.affiliation: Information Technology Laboratory, National Institute of Standards and Technology, USA. Most of this work was done while at the Department of Mathematics and Computer Science, University of Southern Denmark. Part of this work was done while visiting the University of Toronto.
authors.forename: Magnus Gausdal
authors.initials: MG
authors.lastname: Find
authors.affiliation: Information Technology Laboratory, National Institute of Standards and Technology, USA.
authors.forename: René
authors.initials: R
authors.lastname: Peralta