Four Measures of Nonlinearity

Joan Boyar; Magnus Gausdal Find; Rene Peralta

doi:10.1007/978-3-642-38233-8_6

Four Measures of Nonlinearity

Joan Boyar, Magnus Gausdal Find, Rene Peralta

Department of Mathematics and Computer Science

National Institute of Standards and Technology

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

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.

Original language	English
Title of host publication	Algorithms and Complexity - 8th International Conference, CIAC 2013, Proceedings : 8th International Conference, CIAC 2013
Editors	Paul G. Spirakis, Maria Serna
Number of pages	12
Publisher	Springer
Publication date	2013
Pages	61-72
ISBN (Print)	978-3642382321
DOIs	https://doi.org/10.1007/978-3-642-38233-8_6
Publication status	Published - 2013
Event	International Conference on Algorithms and Complexity - Barcelona, Spain Duration: 22. May 2013 → 24. May 2013 Conference number: 8

Conference

Conference	International Conference on Algorithms and Complexity
Number	8
Country/Territory	Spain
City	Barcelona
Period	22/05/2013 → 24/05/2013

Series	Lecture Notes in Computer Science
Volume	7878
ISSN	0302-9743

Documents & Links

10.1007/978-3-642-38233-8_6

8th International Conference on Algorithms and Complexity
Find, M. G. (Speaker)
22. May 2013 → 24. May 2013
Activity: Talks and presentations › Conference presentations

Cite this

@inproceedings{ed7546b7a24646e5ad87bcae83bae0c9,

title = "Four Measures of Nonlinearity",

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 f 1, f 2 with μ 1 (f 1) > μ 1 (f 2) but μ 2(f 1) < μ 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.",

keywords = "Boolean functions, nonlinearity, multiplicative complexity, algebraic degree, annihilator immunity, cryptology",

author = "Joan Boyar and Find, {Magnus Gausdal} and Rene Peralta",

year = "2013",

doi = "10.1007/978-3-642-38233-8_6",

language = "English",

isbn = "978-3642382321",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "61--72",

editor = "Spirakis, {Paul G.} and Maria Serna",

booktitle = "Algorithms and Complexity - 8th International Conference, CIAC 2013, Proceedings",

address = "Germany",

note = "International Conference on Algorithms and Complexity ; Conference date: 22-05-2013 Through 24-05-2013",

}

Boyar, J, Find, MG & Peralta, R 2013, Four Measures of Nonlinearity. in PG Spirakis & M Serna (eds), Algorithms and Complexity - 8th International Conference, CIAC 2013, Proceedings: 8th International Conference, CIAC 2013. Springer, Lecture Notes in Computer Science, vol. 7878, pp. 61-72, International Conference on Algorithms and Complexity, Barcelona, Spain, 22/05/2013. https://doi.org/10.1007/978-3-642-38233-8_6

Four Measures of Nonlinearity. / Boyar, Joan; Find, Magnus Gausdal; Peralta, Rene.
Algorithms and Complexity - 8th International Conference, CIAC 2013, Proceedings: 8th International Conference, CIAC 2013. ed. / Paul G. Spirakis; Maria Serna. Springer, 2013. p. 61-72 (Lecture Notes in Computer Science, Vol. 7878).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Four Measures of Nonlinearity

AU - Boyar, Joan

AU - Find, Magnus Gausdal

AU - Peralta, Rene

N1 - Conference code: 8

PY - 2013

Y1 - 2013

N2 - 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 f 1, f 2 with μ 1 (f 1) > μ 1 (f 2) but μ 2(f 1) < μ 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.

AB - 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 f 1, f 2 with μ 1 (f 1) > μ 1 (f 2) but μ 2(f 1) < μ 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.

KW - Boolean functions

KW - nonlinearity

KW - multiplicative complexity

KW - algebraic degree

KW - annihilator immunity

KW - cryptology

U2 - 10.1007/978-3-642-38233-8_6

DO - 10.1007/978-3-642-38233-8_6

M3 - Article in proceedings

SN - 978-3642382321

T3 - Lecture Notes in Computer Science

SP - 61

EP - 72

BT - Algorithms and Complexity - 8th International Conference, CIAC 2013, Proceedings

A2 - Spirakis, Paul G.

A2 - Serna, Maria

PB - Springer

T2 - International Conference on Algorithms and Complexity

Y2 - 22 May 2013 through 24 May 2013

ER -

Four Measures of Nonlinearity

Abstract

Conference

Documents & Links

Fingerprint

Related activities

8th International Conference on Algorithms and Complexity

Cite this