#### Abstract

This paper studies the properties and constructions of non linear functions, which are a core component of cryptographic primi- tives including data encryption algorithms and one-way hash function. A main contribution of this paper is to reveal the relationship between nonlinearity and propagation characteristic, two critical indicators of the cryptographic strength of a Boolean function. In particular, (we prove that (i) if f, a Boolean function on V_{n}, satisfies the propagation criterion with respect to all but a subset R of vectors in V_{n}, then the nonlinearity of f satisfies N_{f} ≥ 2 ^{n-1} - 2^{1}/_{2}^{(n+t)-1}, where t is the rank of R, and

(ii) When │R│ > 2, the nonzero vectors in R are linearly dependent. Furthermore we show that

(iii) if │R│= 2 then n must be odd, the nonlinearity of f satisfies N_{f }= 2 ^{n-1} - 2 ^{1}/_{2}^{(n-1),} and the nonzero vector in R must be a linear struc- ture of f.

(iv) there exists no function on V_{n} such that │R│ = 3

(v) if │R│ = 4 then n must be even, the nonlinearity of f satisfies N_{f} = 2 ^{n-1} - 2 ^{1}/_{2} ^{n}, and the nonzero vectors in R must be linear structures of f.

(vi) if │R│ = 5 then n must be odd, the nonlinearity of f is N_{f }= 2 ^{n-1} - 2 ^{1}/_{2}^{(n-1)}, the four nonzero vectors denoted by β1, β2, β3 and β4 are related by the equation β1⊕ β2⊕ β3⊕ β4⊕ = 0 and none of the four vectors is a linear structure of f.

(vii) there exists no function on V_{n }such that │R│ = 6.

We also discuss the structures of functions with │R│ = 2,4,5. In particular we show that these functions have close relationships with bent functions, and can be easily constructed from the latter.

## Publication Details

Jennifer Seberry, Xian-Mo Zhang and Yuliang Zheng, Structures of cryptographic functions with strong avalanche characteristics, Advances in Cryptography, ASIACRYPT'94, eds Josef Pieprzyk and Reihaneh Safavi-Naini, Vol 917, Lecture Notes in Computer Science, Springer-Verlag, (1995), 119-132.