Paper 2013/633
Four Measures of Nonlinearity
J. Boyar, 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 collisionfree functions.
Note: Some explanation is made consistent with a revised corollary, which had corrected an error in the CIAC version of the paper.
Metadata
 Available format(s)
 Publication info
 Published elsewhere. Minor revision. Proceedings of CIAC 2013
 Keywords
 Boolean functionsnonlinearitymultiplicative complexityannihilator immunityalgebraic degree
 Contact author(s)
 joan @ imada sdu dk
 History
 20131024: revised
 20131005: received
 See all versions
 Short URL
 https://ia.cr/2013/633
 License

CC BY
BibTeX
@misc{cryptoeprint:2013/633, 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{https://eprint.iacr.org/2013/633}}, url = {https://eprint.iacr.org/2013/633} }