Improved cryptographic properties of Boolean functions obtained from the neighbourhood of Patterson-Wiedemann functions

Abstract

More than a decade ago, the balanced and 1-resilient Boolean functions on 15 variables with the best known nonlinearities 16272 and 16264, respectively, were identifed by interpreting the Patterson-Wiedemann (PW) functions as rotation-symmetric Boolean functions (RSBFs) and performing a deterministic search in their neighbourhood. We here perform an efcient exhaustive search for all the RSBFs belonging to that neighbourhood and enumerate those with the best cryptographic properties, which yields some improvements in terms of algebraic degree, algebraic immunity, and absolute indicator. In the process, by considering the PW functions as 3-RSBFs, we attain balanced Boolean functions with nonlinearity 16268 and absolute indicator 192, which improve the previously best known result in terms of nonlinearity.