High-Meets-Low: Construction of Strictly Almost Optimal Resilient Boolean Functions via Fragmentary Walsh Spectra
Weiguo Zhang · IEEE Transactions on Information Theory · 2019
This paper considers the construction of resilient Boolean functions on an odd number of variables with strictly almost optimal (SAO) nonlinearity. Through introducing the fragmentary Walsh transform, a construction technique called “High-Meets-Low” is proposed. The detailed design procedures of a 39-variable 3-resilient Boolean function with SAO nonlinearity 238- 219+ 216+ 214are given. It is shown that the nonlinearity of an n-variable t-resilient Boolean function can reach 2n-1-2(n-1)/2+5·2(n-11)/2or 2n-1-2(n-1)/2+2(n-7)/2, which are the largest known values for the corresponding n and t values. Finally, by constructing a 29-variable balanced Boolean function with SAO nonlinearity 228-214+ 210+ 29, we show an alternative method to realize the High-Meets-Low construction technique.