Abstract :
High degree of propagation, high nonlinearity, 0-1 balancedness and high algebraic de- gree are crucial criteria for constructing Boolean functions to be used in many cryptosystems for information authentication and data encryption. These criteria are called nonlinearity criteria. An important Boolean problem is that of designing Boolean functions satisfying simultaneously more than one nonlinearity criteria. In this paper we give a necessary and sufficient condition on the Fourier spectrum of a Boolean function, which implies that this function satisfies the propagation criterion with respect to any string in f0; 1g n with odd Hamming weight. We call odd-PC the functions which satisfy this property. We then present a method for constructing balanced odd-PC functions with high algebraic degree and balanced odd-PC functions with high nonlinearity. We also derive a lower bound on the size complexity of odd-PC functions.