Analysis of boolean functions with high second order nonlinearity

Highly nonlinear Boolean functions play a central role in the design and security analysis of high speed stream cyphers and block cyphers. We focus on analyzing the structure of Boolean functions that exhibit high second order nonlinearity. We commence with a theoretical overview of Boolean functions and Reed- Muller codes. We then introduce a new equivalence relation, 2-equivalence, for which we prove a number of important properties. Finally, we analyze the second order nonlinearity of concatenations of two Boolean functions