Projects / Programmes
Designing certain perfect discrete combinatorial objects in spectral domain
| Code |
Science |
Field |
Subfield |
| 1.01.00 |
Natural sciences and mathematics |
Mathematics |
|
| Code |
Science |
Field |
| P001 |
Natural sciences and mathematics |
Mathematics |
| Code |
Science |
Field |
| 1.01 |
Natural Sciences |
Mathematics |
Encryption algorithms, Block ciphers, Differential and linear cryptanalysis, Almost bent functions, APN functions
Researchers (9)
Organisations (2)
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 underlying problem but also due to the lack of more advanced design techniques. Namely, the most common approach is based on the investigation of special kind of polynomials over finite fields which are usually monomials of the form xd 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 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= (f1, ..., fn) 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 a certain progress related to BIG-APN problem.
Significance for science
The problem of classifying and designing APN and AB functions has been actual for the last four decades and currently there is no much understanding related to the essential structure of these objects. Due to practical applications of these functions in cryptography and their connection to other fields in combinatorics, explaining their structure and deriving some efficient construction methods will certainly draw the attention of entire research community in this field to Slovenia and Koper in particular.
This is particularly true when APN permutations for even n ) 6 are considered. Either proving their non-existence or alternatively providing the existence and design of such functions, is an exceptionally hard task and any theoretical progress in this direction can be considered as a tremendous achievement and important contribution to the field.
Another contribution of this project is that our spectral domain design framework can also be useful to handle other related problems in the field. This is a simple consequence of the fact that , at least when cryptographic primitives are concerned, the spectral connection of the encrypted data might give other useful insights related to the design and security.
Significance for the country
The problem of classifying and designing APN and AB functions has been actual for the last four decades and currently there is no much understanding related to the essential structure of these objects. Due to practical applications of these functions in cryptography and their connection to other fields in combinatorics, explaining their structure and deriving some efficient construction methods will certainly draw the attention of entire research community in this field to Slovenia and Koper in particular.
This is particularly true when APN permutations for even n ) 6 are considered. Either proving their non-existence or alternatively providing the existence and design of such functions, is an exceptionally hard task and any theoretical progress in this direction can be considered as a tremendous achievement and important contribution to the field.
Another contribution of this project is that our spectral domain design framework can also be useful to handle other related problems in the field. This is a simple consequence of the fact that , at least when cryptographic primitives are concerned, the spectral connection of the encrypted data might give other useful insights related to the design and security.
Most important scientific results
Interim report
Most important socioeconomically and culturally relevant results
Interim report
