## Cryptology ePrint Archive: Report 2013/633

Four Measures of Nonlinearity

J. Boyar and M.G. Find and R. Peralta

Abstract: Cryptographic applications, such as hashing, block ciphers and stream ciphers, make use of functions which are simple by some criteria (such as circuit implementations), yet hard to invert almost everywhere. A necessary condition for the latter property is to be sufficiently distant'' from linear, and cryptographers have proposed several measures for this distance. In this paper, we show that four common measures, {\em nonlinearity, algebraic degree, annihilator immunity}, and {\em multiplicative complexity}, are incomparable in the sense that for each pair of measures, $\mu_1,\mu_2$, there exist functions $f_1,f_2$ with $\mu_1(f_1)> \mu_1(f_2)$ but $\mu_2(f_1)< \mu_2(f_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.

Category / Keywords: Boolean functions, nonlinearity, multiplicative complexity, annihilator immunity, algebraic degree

Original Publication (with minor differences): Proceedings of CIAC 2013

Date: received 2 Oct 2013, last revised 24 Oct 2013

Contact author: joan at imada sdu dk

Available format(s): PDF | BibTeX Citation

Note: Some explanation is made consistent with a revised corollary, which had corrected an error in the CIAC version of the paper.

[ Cryptology ePrint archive ]