Paper 2013/633

Four Measures of Nonlinearity

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


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.

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

Available format(s)
Publication info
Published elsewhere. Minor revision. Proceedings of CIAC 2013
Boolean functionsnonlinearitymultiplicative complexityannihilator immunityalgebraic degree
Contact author(s)
joan @ imada sdu dk
2013-10-24: revised
2013-10-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {J.  Boyar and M. G.  Find and R.  Peralta},
      title = {Four Measures of Nonlinearity},
      howpublished = {Cryptology ePrint Archive, Paper 2013/633},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.