
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Relationships among Nonlinearity Criteria of Boolean Functions
Shouichi HIROSE Katsuo IKEDA
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E78A
No.2
pp.235243 Publication Date: 1995/02/25
Online ISSN:
DOI:
Print ISSN: 09168508 Type of Manuscript: PAPER Category: Information Security and Cryptography Keyword: Boolean functions, nonlinearity criteria, propagation criterion, strict avalanche criterion, symmetric cryptosystems, cryptography,
Full Text: PDF>>
Summary:
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 ninput 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 ninput 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, ninput 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 ninput Boolean functions satisfying the PC and the sets of those satisfying the SAC.

