A New Construction of Resilient Boolean Functions with High Nonlinearity

Abstract

In this paper, we develop a technique that allows us to obtain new effective constructions of $1$-resilient Boolean functions with very good nonlinearity and autocorrelation. Our strategy to construct a $1$-resilient function is based on modifying a bent function by toggling some of its output bits. Two natural questions that arise in this context are: “At least how many bits and which bits in the output of a bent function need to be changed to construct a $1$-resilient Boolean function?” We present an algorithm that determines a minimum number of bits of a bent function that need to be changed to construct a $1$-resilient Boolean function. We also present a technique to compute points whose output in the bent function need to be modified to get a $1$-resilient function. In particular, the technique is applied up to $14$-variable functions, and we show that the construction provides $1$-resilient functions reaching currently best known nonlinearity and achieving very low autocorrelation absolute indicator values, which were not known earlier.