Combinatorial Problems from Symmetric Cryptography

• Applicants: Dr. Christof Beierle; Dr. Alexandr Polujan
• Subject Area: Mathematics ; Theoretical Computer Science
• Term: since 2026
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 581467925

Almost perfect nonlinear (APN) functions are cryptographically significant mappings between finite fields of even characteristic that provide maximum resistance against differential cryptanalysis. They are also of interest in combinatorics, due to their connection to Sidon sets and incidence structures in finite geometry. Many central questions concerning the construction and classification of these functions remain open. Existing algebraic approaches have produced several important infinite families of APN functions; however, most known constructions yield only a small number of examples in each fixed dimension. Moreover, the combinatorial structure of the entire class of APN functions is still poorly understood. By taking a combinatorial approach, this project aims to address several of these long-standing problems in the design and analysis of APN functions by establishing deeper structural connections between APN functions and one of their main building blocks - perfect nonlinear (also called bent) functions. One of the reasons for the slow progress in this direction has been the limited number of known APN examples in small dimensions. This situation has changed dramatically with the applicants’ recent construction of millions of new quadratic APN functions, achieved by combining complementary theoretical expertise in bent and APN functions with advanced computational techniques. Building on this achievement, the project seeks to uncover deeper combinatorial connections between bent and APN functions and to develop new design methods. The resulting theoretical and computational framework will also allow the transfer of these methods from characteristic two to odd characteristic fields, thereby providing new construction techniques for planar functions - the counterparts of APN functions in odd characteristics.

• DFG Programme: Research Grants