Basic Research Project J1-1694: Designing certain perfect discrete combinatorial 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, a nonlinear mapping of an n-bit block to an m-bit block (so-called a substitution box aka S-box) is an essential cryptographic primitive whose most prominent usage regards the design of a family of symmetric encryption algorithms, commonly termed block ciphers. In particular, two classes of these nonlinear mappings are of immense importance with respect to the two well established cryptanalytic methods differential and linear cryptanalysis. These classes of functions are respectively called APN (almost perfect nonlinear) and AB (almost bent) functions. The former class consists of mappings from $GF(2)^n$ to $GF(2)^n$ that are characterized with the property that their derivatives, that is an equation $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 last 40 years) of finding such mappings for even n ) 6. The latter class of AB functions over $GF(2)^n$, which exist only for odd $n$ and are necessarily APN, achieve the largest possible resistance to linear cryptanalysis. Apart from their applications in cryptography, these functions are also very closely related to design theory and relative difference sets as pointed out by A. Pott in his survey [18]. 

Our main intention is to provide an efficient classification and design of these two classes of functions as it turns out that the known classes of these functions are obtained in non-generic manner. The fact that for both types of functions there are only a few infinite classes of both APN and AB functions is mainly due to the hardness of the underlying problems but also due to the lack of more advanced design techniques. Namely, the most common approach is based on the investigation of a special kind of polynomials over finite fields which are usually monomials of the form $x^d$ for a suitable $d$. This implies that for AB functions, characterized by a certain perfect symmetry in the spectral domain, handling of exponential sums, which is a hard problem in general, related to these functions is simplified. The situation is quite similar in the case of APN functions where most of the theoretical results are again related to monomials. 

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 that has been recently used in [12,13,15] to efficiently specify some interesting classes of Boolean functions which are closely related to APN and AB functions (especially to the latter class). Since this theoretical framework has already been developed for the Boolean case, allowing us to design functions with a desired spectral profile directly in the spectral domain, it remains to understand better what kind of symmetry in spectral domain ensures that a proper selection of $n$ suitably designed Boolean functions implies that $F= (f_1,\ldots, f_n)$ is an APN or AB function. Apart from these results, there are also some further observations that regard certain regularities observed in this context, cf. Section 13. We strongly believe that our recently developed framework provides a proper basis for studying this topic in a different manner, and we are convinced that we will be able to offer either partial or complete solutions to the above-mentioned problems, and possibly to achieve certain progress related to BIG-APN problem.