Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Four Measures of Nonlinearity

Published

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, υ1, υ2, there exist functions f1, f2 with υ1(f1) > υ1(f2) but υ2(f1) < υ2(f2). 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)

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 March 5, 2024)
Created June 22, 2013, Updated October 12, 2021