Four Measures of Nonlinearity

Published

June 23, 2013

Author(s)

Joan Boyar, Magnus Find, Rene 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, nonlinearity, algebraic degree, annihilator immunity, and multiplicative complexity, are incomparable in the sense that for each pair of measures, υ₁, υ₂, there exist functions f₁, f₂ with υ₁(f₁) > υ₁(f₂) but υ₂(f₁) < υ₂(f₂). We also present new connections between two of these measures. Additionally, we give a lower bound on the multiplicative complexity of collision-free functions.

Proceedings Title

8th International Conference on Algorithms and Complexity (CIAC 2013)- Springer Lecture Notes in Computer Science

Volume

7878

Conference Dates

May 22-24, 2013

Conference Location

Barcelona, ES

Conference Title

8th International Conference on Algorithms and Complexity (CIAC 2013)

Pub Type

Conferences

Download Paper

https://doi.org/10.1007/978-3-642-38233-8_6

Local Download

Keywords

nonlinearity measures, annihilator immunity, multiplicative complexity, algebraic degree, collision-free, one-wayness, SHA-3

Citation

Boyar, J. , Find, M. and Peralta, R. (2013), Four Measures of Nonlinearity, 8th International Conference on Algorithms and Complexity (CIAC 2013)- Springer Lecture Notes in Computer Science, Barcelona, ES, [online], https://doi.org/10.1007/978-3-642-38233-8_6, https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=913656 (Accessed April 25, 2026)

Additional citation formats