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.