New constructions of resilient functions with strictly almost optimal nonlinearity via non-overlap spectra functions

The design of n-variable t-resilient functions with strictly almost optimal (SAO) nonlinearity (> 2(n-1) - 2(n/2), n even) appears to be a rather difficult task. The known construction methods commonly use a rather large number (exactly Sigma(n/2)(i=t+1)((n/2)(i))) of affine subfunctions in n/2 variables which can induce some algebraic weaknesses, making these functions susceptible to certain types of guess and determine cryptanalysis and dynamic cube attacks. In this paper, the concept of non-overlap spectra functions is introduced, which essentially generalizes the idea of disjoint spectra functions on different variable spaces. Two, general methods to obtain a large set of non-overlap spectra functions are given and a new framework for designing infinite classes of resilient functions with SAO nonlinearity is developed based on these. Unlike previous construction methods, our approach employs only a few n/2-variable affine subfunctions in the design, resulting in a more favourable algebraic structure. It is shown that these new resilient SAO functions properly include all the existing classes of resilient SAO functions as a subclass. Moreover, it is shown that the new class provides a better resistance against (fast) algebraic attacks than the known functions with SAO nonlinearity, and in addition these functions are more robust to guess and determine cryptanalysis and dynamic cube attacks. (C) 2017 Elsevier Inc. All rights reserved.