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 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.
Metadata
- Available format(s)
-
PDF
- Publication info
- Published elsewhere. Minor revision. Proceedings of CIAC 2013
- Keywords
- Boolean functionsnonlinearitymultiplicative complexityannihilator immunityalgebraic degree
- Contact author(s)
- joan @ imada sdu dk
- History
- 2013-10-24: revised
- 2013-10-05: 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},
url = {https://eprint.iacr.org/2013/633}
}
