Highly Nonlinear 0-1 Balanced Boolean Functions Satisfying Strict Avalanche Criterion

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\n(i) 0-1 balanced boolean functions on V2k+1 (k ≥ 1) having nonlinearity 22k - 2k and satisfying SAC,\n(ii) 0-1 balanced boolean functions on V2k (k ≥ 2) having nonlinearity 22k-1 - 2k and satisfying SAC.\nWe 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.