Highly nonlinear 0-1 balanced boolean functions satisfying strict avalanche criterion

Authors

Jennifer Seberry, University of WollongongFollow
Xian-Mo Zhang, University of WollongongFollow

Publication Details

Jennifer Seberry and Xian-Mo Zhang, Highly nonlinear 0-1 balanced boolean functions satisfying strict avalanche criterion, (Jennifer Seberry and Yuliang Zheng, (Eds.)), Advances in Cryptography - Auscrypt'92, Conference held at the Gold Coast, Australia, December 1992, 718, Lecture Notes in Computer Science, Springer-Verlag, Berlin--Heidelberg--New York, (1993), 145-155.

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 V_2k+1 (k ≥ 1) having nonlinearity 2^2k - 2^k and satisfying SAC,

(ii) 0-1 balanced boolean functions on V_2k (k ≥ 2) having nonlinearity 2^2k-1 - 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.