Boolean Functions: Cryptographic and Combinatorial Properties - Functions with Symmetry

This book discusses cryptographic and combinatorial properties of Boolean functions. Boolean functions are very easy to understand (but deep in analysis) and the subject covers significant amount of material in digital circuits, communication theory, VLSI design, computer science, coding theory and Mathematics. Boolean function is considered as one of the most basic building blocks in cryptographic system design. The properties that make a Boolean function suitable for a cryptographic system, are mostly combinatorial. We discuss these properties (e.g., balancedness, nonlinearity, correlation immunity, propagation characteristics, algebraic immunity) in detail. For each of the properties, existing research results and the recent contributions in the literature will be presented. The basic material will always contain hardcore theoretical results. However, we present the materials in a way that a person with undergraduate level mathematical background can access it. Implementation details related to these properties (e.g., how to check in writing a program whether a Boolean function is correlation immune) will be detailed. In addition to theoretical construction techniques for Boolean functions with different combinatorial and cryptographic properties, the book will concentrate on different state-of-the-art search techniques. In some cases these search techniques provide better results than the construction techniques for low number of input variables and they are quite interesting as the size of the complete set of Boolean functions is super exponential in the number of input variables. Different symmetries in the set of Boolean functions will also be presented in detail. The author will present the inherent beauty of Boolean functions that he has experienced in his research career.