Article Contents
Article Contents

# Generalized nonlinearity of $S$-boxes

• * Corresponding author: Goutam Paul
• While analyzing $S$-boxes, or vectorial Boolean functions, it is of interest to approximate its component functions by affine functions. In the usual attack models, it is assumed that all input vectors to an $S$-box are equiprobable. The nonlinearity of an $S$-box is defined, subject to this assumption. In this paper, we explore the possibility of linear cryptanalysis of an $S$-box by introducing biased inputs and thus propose a generalized notion of nonlinearity along with a generalization of the Walsh-Hadamard spectrum of an $S$-box.

Mathematics Subject Classification: Primary: 06E30, 11T71; Secondary: 94A60.

 Citation:

• Table 1.  Maximum bias without and with biased inputs for all DES S-boxes.

 $F$ $S_1$ $S_2$ $S_3$ $S_4$ $S_5$ $S_6$ $S_7$ $S_8$ $\displaystyle \max_{{\bf{u}} \in {\mathbb{F}}_2^n}\epsilon({\bf{u}}, {\bf{v}} \cdot F)$ 0.219 0.219 0.219 0.156 0.219 0.188 0.281 0.188 $\displaystyle \max_{{\bf{u}} \in {\mathbb{F}}_2^n} \epsilon^{(p)}_{{\mathcal{S}}}({\bf{u}}, {\bf{v}}\cdot F)$ 0.494 0.494 0.497 0.489 0.494 0.491 0.494 0.494
•  P. Erdös  and  A. Rényi , On the evolution of random graphs, Publ. Math. Inst. Hungar. Acad. Sci., 5 (1960) , 17-61. E. Friedgut  and  Gil Kalai , Every monotone graph property has a sharp threshold, Proc. AMS, 124 (1996) , 2293-3002. S. Gangopadhyay , A. Kar Gangopadhyay , S. Pollatos  and  P. Stǎnicǎ , Cryptographic Boolean functions with biased inputs, Crypt. Commun. Discrete Struct. Seq., 9 (2017) , 301-314. Y. Lu and Y. Desmedt, Bias analysis of a certain problem with applications to E0 and Shannon ciper, in ICISC 2010, 2011, 16-28. M. Matsui, Linear cryptanalysis method for DES cipher, in EUROCRYPT'93, Springer, 1994,386-397. R. O'Donnell, Analysis of Boolean Functions, Cambridge Univ. Press, 2014. M. G. Parker, Generalised S-box nonlinearity, NESSIE Public Document, 11. 02. 03: NES/DOC/UIB/WP5/020/A. D. R. Stinson, Cryptography: Theory and Practice, 3rd Edition, Chapman and Hall/CRC, 2005.

Tables(1)