Customized Project N1-0159: Designing certain discrete mathematical objects in spectral domain

Abstract:

The main goal of this project is to investigate the existence, design and classification of certain discrete combinatorial objects that correspond to a special class of polynomials over finite fields which play an important role in cryptography. Namely, our main interest is the analysis of the so-called APN (almost perfect nonlinear) and AB (almost bent) functions. Our main intention is to provide an efficient classification and design of these two classes of functions since the known classes of these functions are obtained in non-generic and non-systematic manner.

The approach that we will be using and developing in this project can be viewed as a reversed engineering in a certain sense. More precisely, instead of trying to solve some intrinsically hard problems related to exponential sums (which appears not to be realistic) we will attempt to extend the so-called spectral design method to efficiently specify some interesting classes of Boolean functions that are closely related to APN and AB functions in the spectral domain. Thus, it remains to understand better what kind of symmetry in spectral domain ensures that a proper selection of $n$ suitably designed Boolean functions $f_i$ implies that $F= (f_1,\ldots, f_n)$ is an APN or AB function. A simple additional 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 last 40 years) of finding such mappings for even $n\geq 6$. Apart from the above-mentioned results, there are also some further observations that regard certain regularities observed in this context. We strongly believe that spectral framework provides a proper basis for studying this topic in a different manner, eventually allowing us to offer either partial or complete solutions to the above mentioned problems (including the BIG APN problem).