| On the approximation of S-boxes via Maiorana-McFarland functions |
| Wei, Yongzhuang (1)
; Pasalic, Enes (3)
|
刊名 | IET Information Security
![](/image/waiting.gif) |
| 2013
|
卷号 | 7期号:2页码:134-143 |
ISSN号 | 17518709
|
中文摘要 | Substitution boxes (S-boxes) are the key components of conventional cryptographic systems. To quantify the confusion property of S-boxes, different non-linearity criteria are proposed such as usual non-linearity (NF), unrestricted nonlinearity (UNF), generalised non-linearity (GN F), higher order non-linearity (HNF) and so on. Although these different criteria come from the idea of linear (or non-linear) approximation of S-boxes, the algebraic structures of Boolean functions that are used to approximate to S-boxes have not been considered yet. In this study, the concept of the extended non-linearity of S-boxes (denoted by ENF) is introduced by measuring the distance of a given function to a subset of Maiorana-McFarland functions. This approximation appears to be appealing because of a particular structure of this class of functions, namely their representation as a concatenation of affine functions. The complexity of computing the rth order extended non-linearity for S-boxes over GF(2) n is less than O ((n/r)2n-r), (r > 1). Moreover, a theoretical upper bound for the rth order extended nonlinearity is proved, which is much lower than previous generalised non-linearity which might give a rise to more efficient attacks that combine a generalised correlation approach with guess and determine techniques. Furthermore, the relationship between the r-order extended non-linearity and the generalised non-linearity is derived. © The Institution of Engineering and Technology 2013. |
英文摘要 | Substitution boxes (S-boxes) are the key components of conventional cryptographic systems. To quantify the confusion property of S-boxes, different non-linearity criteria are proposed such as usual non-linearity (NF), unrestricted nonlinearity (UNF), generalised non-linearity (GN F), higher order non-linearity (HNF) and so on. Although these different criteria come from the idea of linear (or non-linear) approximation of S-boxes, the algebraic structures of Boolean functions that are used to approximate to S-boxes have not been considered yet. In this study, the concept of the extended non-linearity of S-boxes (denoted by ENF) is introduced by measuring the distance of a given function to a subset of Maiorana-McFarland functions. This approximation appears to be appealing because of a particular structure of this class of functions, namely their representation as a concatenation of affine functions. The complexity of computing the rth order extended non-linearity for S-boxes over GF(2) n is less than O ((n/r)2n-r), (r > 1). Moreover, a theoretical upper bound for the rth order extended nonlinearity is proved, which is much lower than previous generalised non-linearity which might give a rise to more efficient attacks that combine a generalised correlation approach with guess and determine techniques. Furthermore, the relationship between the r-order extended non-linearity and the generalised non-linearity is derived. © The Institution of Engineering and Technology 2013. |
收录类别 | SCI
; EI
|
语种 | 英语
|
WOS记录号 | WOS:000321701300010
|
公开日期 | 2014-12-16
|
内容类型 | 期刊论文
|
源URL | [http://ir.iscas.ac.cn/handle/311060/16956] ![](/themes/default/image/downing1.png) |
专题 | 软件研究所_软件所图书馆_期刊论文
|
推荐引用方式 GB/T 7714 |
Wei, Yongzhuang ,Pasalic, Enes . On the approximation of S-boxes via Maiorana-McFarland functions[J]. IET Information Security,2013,7(2):134-143.
|
APA |
Wei, Yongzhuang ,&Pasalic, Enes .(2013).On the approximation of S-boxes via Maiorana-McFarland functions.IET Information Security,7(2),134-143.
|
MLA |
Wei, Yongzhuang ,et al."On the approximation of S-boxes via Maiorana-McFarland functions".IET Information Security 7.2(2013):134-143.
|
修改评论