**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)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]