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.

Version: 20131024:122758 (All versions of this report)

Short URL: ia.cr/2013/633

Discussion forum: Show discussion | Start new discussion