Highly Nonlinear 0-1 Balanced Boolean Functions Satisfying Strict Avalanche Criterion (Extended Abstract)

) Jennifer Seberry Xian-Mo Zhang y Department of Computer Science The University of Wollongong Wollongong, NSW 2522, AUSTRALIA Abstract Nonlinearity, 0-1 balancedness and strict avalanche criterion (SAC) are important criteria for cryptographic functions. Bent functions have maximum nonlinearity and satisfy SAC however they are not 0-1 balanced and hence cannot be directly used in many cryptosystems where 0-1 balancedness is needed. In this paper we construct (i) 0-1 balanced boolean functions on V2k+1 (k ? = 1) having nonlinearity 2 2k \Gamma 2 k and satisfying SAC, (ii) 0-1 balanced boolean functions on V2k (k ? = 2) having nonlinearity 2 2k\Gamma1 \Gamma 2 k and satisfying SAC. We demonstrate that the above nonlinearities are very high not only for the 0-1 balanced functions satisfying SAC but also for all 0-1 balanced functions. 1 Basic Definitions Let Vn be the vector space of n tuples of elements from GF (2). Let ff; fi 2 Vn . Write ff = (a 1 \Delta \Delta \Delt..