On the nonlinearity of S-boxes and linear codes
详细信息 查看全文
- 作者：Jian Liu ; Sihem Mesnager ; Lusheng Chen
- 关键词：Symmetric cryptography ; Multi ; output Boolean functions ; S ; boxes ; Affine approximation attack ; Nonlinearity ; Linear codes
- 刊名：Cryptography and Communications
- 出版年：2017
- 出版时间：May 2017
- 年：2017
- 卷：9
- 期：3
- 页码：345-361
- 全文大小：
- 刊物类别：Computer Science
- 刊物主题：Data Structures, Cryptology and Information Theory; Coding and Information Theory; Communications Engineering, Networks; Information and Communication, Circuits; Mathematics of Computing;
- 出版者：Springer US
- ISSN：1936-2455
- 卷排序：9
文摘
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.