Construction of Nonlinear Resilient Boolean Functions Using “Small” Affine Functions
Palash Sarkar, Subhamoy Maitra · IEEE Transactions on Information Theory · 2004
In this correspondence, we use affine functions on a small number of variables to construct resilient functions on a large number of variables. We show that by properly combining these functions it is possible to achieve high nonlinearity and high algebraic degree. An important contribution of the correspondence is to show that for each order of resiliency m, it is possible to find infinitely many odd and even positive integers n, such that it is possible to construct (maximum degree) n-variable, m-resilient functions having nonlinearity strictly greater than 2/sup n-1/-2/sup /spl lfloor/n/2/spl rfloor//. We also present construction of some important functions on a small number of variables.