Propagation Characteristics of Boolean Functions and Their Balancedness

Shouichi HIROSE  Katsuo IKEDA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E78-A   No.1   pp.11-18
Publication Date: 1995/01/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: 
Keyword: 
Boolean functions,  nonlinearity criteria,  propagation criterion,  balancedness,  symmetric cryptosystems,  

Full Text: PDF>>
Buy this Article




Summary: 
This paper discusses Boolean functions satisfying the propagation criterion (PC) and their balancedness. Firstly, we discuss Boolean functions with n variables that satisfy the PC with respect to all but three elements in {0,1}n-{(0,...,0)}. For even n4, a necessary and sufficient condition is presented for Boolean functions with n variables to satisfy the PC with respect to all but three elements in {0,1}n-{(0,...,0)}. From this condition, it is proved that all of these Boolean functions are constructed from all perfectly nonlinear Boolean functions with n-2 variables. For odd n3, it is shown that Boolean functions with n variables satisfying the PC with respect to all but three elements in {0,1}n-{(0,...,0)} satisfy the PC with respect to all but one elements in it. Secondly, Boolean functions satisfying the PC of degree n-2 and their balancedness are considered. For even n4, it is proved that an upper bound on the degree of the PC is n-3 for balanced Boolean functions with n variables. This bound is optimal for n=4,6. It is also proved that, for odd n3, balanced Boolean functions with n variables satisfying the PC of degree n-2 satisfy the PC with respect to all but one elements in {0,1}n-{(0,...,0)}.