Complexity of Boolean functions satisfying the propagation criterion

Complexity of Boolean functions satisfying the propagation criterion(PC), an extended notion of the perfect nonlinearity, is discussed on several computation models. The following topics are investigated; (i) relationships between the unateness and the degree of the PC, (ii) the inversion complexity of perfectly nonlinear Boolean functions, (iii) the formula size of Boolean functions that satisfy the PC of degree 1, (iv) the area-time-square complexity of VLSI circuits computing perfectly nonlinear Boolean functions, (v) the OBDD size of perfectly nonlinear Boolean functions. 1 Introduction The aim of this paper is to characterize the PC in terms of the complexity of Boolean functions satisfying the criterion. Nonlinearity is an important concept for the design of conventional cryptosystems. The propagation criterion(PC)[8], which is a generalized notion of the perfect nonlinearity[6], is a nonlinearity criteria of Boolean functions. The PC is a measure of randomness of the differen..