Cryptological viewpoint of Boolean function

Sağdıçoğlu, Serhat
Boolean functions are the main building blocks of most cipher systems. Various aspects of their cryptological characteristics are examined and investigated by many researchers from different fields. This thesis has no claim to obtain original results but consists in an attempt at giving a unified survey of the main results of the subject. In this thesis, the theory of boolean functions is presented in details, emphasizing some important cryptological properties such as balance, nonlinearity, strict avalanche criterion and propagation criterion. After presenting many results about these criteria with detailed proofs, two upper bounds and two lower bounds on the nonlinearity of a boolean function due to Zhang and Zheng are proved. Because of their importance in the theory of boolean functions, construction of Sylvester-Hadamard matrices are shown and most of their properties used in cryptography are proved. The Walsh transform is investigated in detail by proving many properties. By using a property of Sylvester-Hadamard matrices, the fast Walsh transform is presented and its application in finding the nonlinearity of a boolean function is demonstrated. One of the most important classes of boolean functions, so called bent functions, are presented with many properties and by giving several examples, from the paper of Rothaus. By using bent functions, relations between balance, nonlinearity and propagation criterion are presented and it is shown that not all these criteria can be simultaneously satisfied completely. For this reason, several constructions of functions optimizing these criteria which are due to Seberry, Zhang and Zheng are presented.
Citation Formats
S. Sağdıçoğlu, “Cryptological viewpoint of Boolean function,” M.S. - Master of Science, Middle East Technical University, 2003.