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

Abstract

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\ge 12$ even, $1<m\le \lfloor n/4\rfloor )$ 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.

Keywords:

• stream ciphers
• S-boxes
• fast algebraic attacks
• disjoint linear codes
• dual codes

2010 AMS Subject Classifications:

• 94A60
• 14G50
• 06E30

Acknowledgements

The authors would like to thank the anonymous referees and the editors for their helpful comments and kind suggestions.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Funding

Yongzhuang Wei was supported in part by the Natural Science Foundation of China [61100185, 61201250], in part by the National Basic Research Program of China [2013CB338002], in part by the project of Outstanding Young Teachers' Training in Higher Education Institutions of Guangxi. Enes Pasalic was in part supported by the Slovenian Research Agency research program [P3-0384] and research project [J1-6720]. Fengrong Zhang was supported in part by National Science Foundation of China [61303263], in part by the Fundamental Research Funds for the Central Universities [2013QNA26], in part by the China Postdoctoral Science Foundation funded project [2014M562494], and in part by the Jiangsu Planned Projects for Postdoctoral Research Funds [1401056B].