On the nonlinearity of S-boxes and linear codes

Abstract

For multi-output Boolean functions (also called S-boxes), various measures of nonlinearity have been widely discussed in the literature but many problems are left open in this topic. The purpose of this paper is to present a new approach to estimating the nonlinearity of S-boxes. A more fine-grained view on the notion of nonlinearity of S-boxes is presented and new connections to some linear codes are established. More precisely, we mainly study the nonlinearity indicator (denoted by \(\mathcal {N}_{\mathrm {v}}\) ) for S-boxes from a coding theory point of view. Such a cryptographic parameter \(\mathcal {N}_{\mathrm {v}}\) is more related to best affine approximation attacks on stream ciphers. We establish a direct link between \(\mathcal {N}_{\mathrm {v}}\) and the minimum distance of the corresponding linear code. We exploit that connection to derive the first general lower bounds on \(\mathcal {N}_{\mathrm {v}}\) of non-affine functions from \(\mathbb {F}_{2^{n}}\) to \(\mathbb {F}_{2^{m}}\) for m dividing n. Furthermore, we show that \(\mathcal {N}_{\mathrm {v}}\) can be determined directly by the weight distribution of the corresponding linear code.

from #AlexandrosSfakianakis via Alexandros G.Sfakianakis on Inoreader http://ift.tt/2lofnS3
via IFTTT