GLOBAL AVALANCHE CHARACTERISTICS AND NONLINEARITY OF BALANCED BOOLEANFUNCTIONS

The GAC (global avalanche characteristic) was introduced to measure cr yptographic behavior, such as, propagation characteristic, in a global manner. The two indicators sigma(f) and Delta(f) related to GAC are i ntroduced. However, an important problem to compute lower bounds of tw o indicators for balanced Boolean functions was not solved yet. In thi s paper, we derive lower bounds on the two indicators for balanced Boo lean functions: sigma f greater than or equal to 2(2n) + 2(n+3) and De lta(f) greater than or equal to 8. Moreover, we obtain an upper bound on nonlinearity for balanced Boolean functions: N-f less than or equal to 2(n-1) - 1/2 2(-n/2) root sigma(f), which improves the previously known results. (C) 1998 Published by Elsevier Science B.V.