Discrete combinatorial objects in the spectral domain - intersection analysis

The main goal of this project is to provide further analysis regarding certain combinatorial objects that are of crucial importance in cryptography, stemming from certain hard problems in discrete mathematics that involve discrete exponential sums. More precisely, there exist special classes of polynomials over finite fields that possess exceptional (optimal) properties with respect to two well established cryptanalytic methods differential and linear cryptanalysis. These classes of functions (polynomials) are respectively called APN (almost perfect nonlinear) and AB (almost bent) functions whose generic design methods have still not been developed. These functions are also very closely related to design theory and relative difference sets. APN functions are mappings from GF(2)^n to GF(2)^n that are characterized by the property that the equation of the form F(x⊕a)⊕F(x)=b over GF(2)^n, admit either 0 or 2 solutions for any nonzero a and any b in GF(2)^n. A simple requirement that an APN mapping F is also a permutation, for even n, leads to an extremely difficult problem (commonly called BIG APN problem, which has been open for the last 40 years) of finding such mappings for even n >6. On the other hand, AB functions over GF(2)^n, which exist only for odd n and are necessarily APN, achieve the largest possible resistance to linear cryptanalysis. Our main intention is to deepen our previous attempts towards finding generic solutions related to the design and classification of these functions. Whereas traditional methods are mostly focused on the analysis of simple polynomial forms over finite fields (monomials and binomials), the applicant of this project (along with other members of the crypto group at UP FAMNIT) has already started investigations in the spectral domain which translates these problems (using Fourier/Walsh transform) into the specification of suitable spectral values for the coordinate functions (representing the finite field as a vector space). In the context of AB functions, these coordinate functions can be easily specified in the spectral domain using the existing design techniques (especially those proposed recently inf [16, 18, 19, 20]) but the main challenge is to ensure that their linear combinations preserve the desired spectral distributions. An initial analysis taken recently in [1], indicates a regular behaviour of the nonzero spectral values of the coordinate functions. More precisely, these values essentially define subspaces of certain dimension, and their suitable intersection (along with the sign assignment) seems to be decisive for deriving these perfect combinatorial objects such as AB functions. Today, almost nothing is known about the behaviour of these intersections together with a suitable sign assignment of the spectral values. The only results in this direction were obtained recently in [1] using a sophisticated computer search, where certain classes of AB functions were constructed for relatively small odd n < 9. A further analysis and better understanding of the results obtained by computer simulations is therefore necessary. The situation is quite similar in the case of APN functions where most of the theoretical results are again related to monomials or binomials. Especially, when n is even, the known APN families contain a certain number of so-called bent functions. Commonly, the remaining component functions are either semi-bent or 5-valued spectra functions and again their mutual interaction must be perfect to build an APN function. We strongly believe that different classes of bent functions embedded in APN functions will give structurally different objects, which is a reasonable hypothesis and starting initiative for the proposed project. Our ultimate goal is to investigate the behaviour of the component functions in the spectral domain and to develop theoretical results related to the design of both AB and APN functions.