Upper and lower bounds on maximum nonlinearity of n-input m-output Booleanfunction

Citation
T. Wadayama et al., Upper and lower bounds on maximum nonlinearity of n-input m-output Booleanfunction, DES CODES C, 23(1), 2001, pp. 23-33
Citations number
11
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Computer Science & Engineering
Journal title
DESIGNS CODES AND CRYPTOGRAPHY
ISSN journal
0925-1022 → ACNP
Volume
23
Issue
1
Year of publication
2001
Pages
23 - 33
Database
ISI
SICI code
0925-1022(200105)23:1<23:UALBOM>2.0.ZU;2-H
Abstract
The paper presents lower and upper bounds on the maximum nonlinearity for a n n-input m-output Boolean function. We show a systematic construction meth od for a highly nonlinear Boolean function based on binary linear codes whi ch contain the first order Reed-Muller code as a subcode. We also present a method to prove the nonexistence of some nonlinear Boolean functions by us ing nonexistence results on binary linear codes. Such construction and none xistence results can be regarded as lower and upper bounds on the maximum n onlinearity. For some n and m, these bounds are tighter than the convention al bounds. The techniques employed here indicate a strong connection betwee n binary linear codes and nonlinear n-input in-output Boolean functions.