A New Construction of Resilient Boolean Functions with High Nonlinearity

Abstract

In this paper we develop a technique that allows us to obtainnew effective construction of 1-resilient Boolean functions with verygood nonlinearity and autocorrelation. Our strategy to construct a1-resilient function is based on modifying a bent function, by togglingsome 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 abent function need to be changed to construct a 1resilient Booleanfunction. We present an algorithm which determines a minimumnumber of bits of a bent function that need to be changed to constructa 1-resilient Boolean function. We also present a technique to compute points whose output in the bent function need to be modified toget a 1-resilient function. In particular, the technique is applied upto14-variable functions and we show that the construction provides 1-resilient functions reaching currently best known nonlinearity andachieving very low autocorrelation absolute indicator values whichwere not known earlier.