On algebraic properties of S-boxes designed by means of disjoint linear codes

In a recent paper[W. Zhang and E. Pasalic, Constructions of resilient S-Boxes with strictly almost optimal nonlinearity through disjoint linear codes, IEEE Trans Inf Theory 60, no. 3 (2014), pp. 1638-1651], by using disjoint linear codes, Zhang and Pasalic presented a method for constructing t-resilient S-boxes F : GF(2)(n) --> GF(2)(m)(n >= 12 even, l M m <= left perpendicular n/4 right perpendicular) with strictly almost optimal (currently best) nonlinearity exceeding the value 2(n-1) - 2(n/2). It was also shown that the algebraic degree and algebraic immunity of these resilient S-boxes are very good, but the resistance of these resilient S-boxes against fast algebraic attacks has not been treated in[W. Zhang and E. Pasalic,Constructions of resilient S-Boxes with strictly almost optimal nonlinearity through disjoint linear codes, IEEE Trans. Inf. Theory 60, no. 3 (2014), pp. 1638-1651]. In this work, we extend the method originally proposed in[E. Pasalic,Maiorana-McFarland class: Degree optimization and algebraic properties, IEEE Trans. Inf. Theory 52, no. 10 (2006), pp. 4581-4595] and used in deriving the upper bound on algebraic immunity of the Maiorana-McFarland class, for establishing the existence of low degree multiplier for the class of S-boxes that uses disjoint linear codes in the design. It is demonstrated that this class of functions has a substantial weakness against fast algebraic cryptanalysis. An alternative approach, based on the use of the associated dual codes is also developed.