Covering sequences and t, k-bentness criteria

Kurnaz, Güzin
This dissertation deals with some crucial building blocks of cryptosystems in symmetric cryptography; namely the Boolean functions that produce a single-bit result for each possible value of the m-bit input vector, where m>1. Objectives in this study are two-fold; the first objective is to develop relations between cryptographic properties of Boolean functions, and the second one is to form new concepts that associate coding theory with cryptology. For the first objective, we concentrate on the cryptographic properties of Boolean functions such as balancedness, correlation immunity, nonlinearity, resiliency and propagation characteristics; many of which are depending on the Walsh spectrum that gives components of the Boolean function along the direction of linear functions. Another efficient tool to study Boolean functions is the subject of covering sequences introduced by Carlet and Tarannikov in 2000. Covering sequences are defined in terms of the derivatives of the Boolean function. Carlet and Tarannikov relate the correlation immunity and balancedness properties of the Boolean function to its covering sequences. We find further relations between the covering sequence and the Walsh spectrum, and present two theorems for the calculation of covering sequences associated with each null frequency of the Walsh spectrum. As for the second objective of this thesis, we have studied linear codes over the rings Z4 and Z8 and their binary images in the Galois field GF(2). We have investigated the best-known examples of nonlinear binary error-correcting codes such as Kerdock, Preperata and Nordstrom-Robinson, which are -linear codes. We have then reviewed Tokareva’s studies on Z4-linear codes and extended them to Z8-linear codes. We have defined a new classes of bent functions. Next, we have shown that the newly defined classes of bent, namely Tokareva’s k-bent and our t,k-bent functions are affine equivalent to the well-known Maiorana McFarland class of bent functions. As a cryptological application, we have described the method of cubic cryptanalysis, as a generalization of the linear cryptanalysis given by Matsui in 1993. We conjecture that the newly introduced t,k-bent functions are also strong against cubic cryptanalysis, because they are as far as possible to t,k-bent functions.
Citation Formats
G. Kurnaz, “Covering sequences and t, k-bentness criteria,” Ph.D. - Doctoral Program, Middle East Technical University, 2009.