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

Wadayama, T Hada, T Wakasugi, K Kasahara, M

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

11

INGLESE

Article

Computer Science & Engineering

DESIGNS CODES AND CRYPTOGRAPHY

0925-1022 → ACNP

23

1

2001

23 - 33

ISI

0925-1022(200105)23:1<23:UALBOM>2.0.ZU;2-H

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.