Highly nonlinear balanced S-boxes with improved bound on unrestricted and generalized nonlinearity

摘要

We construct two classes of balanced S-boxes with high nonlinearity 2(n-1) - 2((n-1)/2) for n odd. From known results, it can be deduced that for any S-box which has nonlinearity 2(n-1) -2((n-1)/2) , the unrestricted nonlinearity is lower bounded by 2(n-1) -2((m+n-1)/2) while the generalized nonlinearity is lower bounded by 2(n-1) -(2(m) -1) 2((n-1)/2). We prove that the lower bound on the unrestricted nonlinearity of both our S-box constructions can be increased to 2(n-1) -2((m+n)/2-1). For the first class of S-box, the lower bound on generalized nonlinearity can be increased to 2(n-1) -2((n-1)/2+m-1). For the second class, the generalized nonlinearity is proven to be exactly 2(n-1) -2((m+n)/2-1), which is much higher than the lower bound for our first construction. The first class of S-boxes have low maximum differential while the second class corresponds to GMW sequences, whose algebraic structure allows us to construct a larger family of S-boxes. Moreover, both classes of S-boxes can attain high algebraic degree. We also compare our constructions with some known functions with high unrestricted and/or generalized nonlinearity.