Relationships among Nonlinearity Criteria of Boolean Functions

Shouichi HIROSE  Katsuo IKEDA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E78-A   No.2   pp.235-243
Publication Date: 1995/02/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Information Security and Cryptography
Boolean functions,  nonlinearity criteria,  propagation criterion,  strict avalanche criterion,  symmetric cryptosystems,  cryptography,  

Full Text: PDF>>
Buy this Article

For symmetric cryptosystems, their transformations should have nonlinear elements to be secure against various attacks. Several nonlinearity criteria have been defined and their properties have been made clear. This paper focuses on, among these criteria, the propagation criterion (PC) and the strict avalanche criterion (SAC), and makes a further investigation of them. It discusses the sets of Boolean functions satisflying the PC of higher degrees, the sets of those satisfying the SAC of higher orders and their relationships. We give a necessary and sufficient condition for an n-input Boolean function to satisfy the PC with respect to a set of all but one or two elements in {0,1}n{(0,...,0)}. From this condition, it follows that, for every even n 2, an n-input Boolean function satisfies the PC of degree n 1 if and only if it satisfies the PC of degree n. We also show a method that constructs, for any odd n 3, n-input Boolean functions that satisfy the PC with respect to a set of all but one elements in {0,1}n{(0,...,0)}. This method is a generalized version of a previous one. Concerned with the SAC of higher orders, it is shown that the previously proved upper bound of the nonlinear order of Boolean functions satisfying the criterion is tight. The relationships are discussed between the set of n-input Boolean functions satisfying the PC and the sets of those satisfying the SAC.