Characterizing the structures of cryptographic functions satisfying the propagation criterion for almost all vectors

Many practical information authentication techniques are based on such cryptographic means as data encryption algorithms and one-way hash functions. A core component of such algorithms and functions are nonlinear functions. In this paper, we reveal a relationship between nonlinearity and propagation characteristic, two critical indicators of the cryptographic strength of a Boolean function. We also investigate the structures of functions that satisfy the propagation criterion with respect to all but six or less vectors. We show that these functions have close relationships with bent functions, and can be easily constructed from the latter.