Title: On the approximation of S-boxes via Maiorana-McFarland functions

Author: Wei, Yongzhuang (1)
; Pasalic, Enes (3)
Source: IET Information Security
Issued Date: 2013
Volume: 7, Issue: 2, Pages: 134-143 Indexed Type: SCI
; EI
Department: (1) State Key Laboratory of Information Security, Institute of Software, Chinese Academy of Sciences, Beijing 100190, China; (2) Guilin University of Electronic Technology, Guilin City, Guangxi Province 541004, China; (3) University of Primorska, FAMNIT and IAM, 6000, Koper, Slovenia
Abstract: 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)2^{n-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.
English Abstract: 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)2^{n-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.
Language: 英语
WOS ID: WOS:000321701300010
Citation statistics:

Content Type: 期刊论文
URI: http://ir.iscas.ac.cn/handle/311060/16956
Appears in Collections: 软件所图书馆_期刊论文

There are no files associated with this item.

Recommended Citation:
Wei, Yongzhuang ,Pasalic, Enes . On the approximation of S-boxes via Maiorana-McFarland functions[J]. IET Information Security,2013-01-01,7(2):134-143.