Propagation Characteristics of Boolean Functions and Their Balancedness

概要

論文の詳細を見る
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 n≧4, 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 n≧3, 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 n≧4, 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 n≧3, 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)}.
社団法人電子情報通信学会の論文
1995-01-25