Relationships among Nonlinearity Criteria of Boolean Functions

概要

論文の詳細を見る
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 satisfying 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.
社団法人電子情報通信学会の論文
1995-02-25