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

Institut for Matematik og Datalogi

National Institute of Standards and Technology

Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › 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.

Originalsprog	Engelsk
Titel	Algorithms and Complexity - 8th International Conference, CIAC 2013, Proceedings : 8th International Conference, CIAC 2013
Redaktører	Paul G. Spirakis, Maria Serna
Antal sider	12
Forlag	Springer
Publikationsdato	2013
Sider	61-72
ISBN (Trykt)	978-3642382321
DOI	https://doi.org/10.1007/978-3-642-38233-8_6
Status	Udgivet - 2013
Begivenhed	International Conference on Algorithms and Complexity - Barcelona, Spanien Varighed: 22. maj 2013 → 24. maj 2013 Konferencens nummer: 8

Konference

Konference	International Conference on Algorithms and Complexity
Nummer	8
Land/Område	Spanien
By	Barcelona
Periode	22/05/2013 → 24/05/2013

Navn	Lecture Notes in Computer Science
Vol/bind	7878
ISSN	0302-9743

Emneord

Boolean functions
nonlinearity
multiplicative complexity
algebraic degree
annihilator immunity
cryptology

Dokumenter og links

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

SDU link

Tjek adgangen til materialet i Syddansk Universitetsbiblioteks søgemaskine

Citationsformater

@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. i PG Spirakis & M Serna (red), Algorithms and Complexity - 8th International Conference, CIAC 2013, Proceedings: 8th International Conference, CIAC 2013. Springer, Lecture Notes in Computer Science, bind 7878, s. 61-72, International Conference on Algorithms and Complexity, Barcelona, Spanien, 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. red. / Paul G. Spirakis; Maria Serna. Springer, 2013. s. 61-72 (Lecture Notes in Computer Science, Bind 7878).

Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › 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

Konference

Emneord

Dokumenter og links

SDU link

Fingeraftryk

Citationsformater