Page 150 - Ellingham, Mark, Mariusz Meszka, Primož Moravec, Enes Pasalic, 2014. 2014 PhD Summer School in Discrete Mathematics. Koper: University of Primorska Press. Famnit Lectures, 3.
P. 150
4.4 Vectorial Boolean functions - substitution boxes
The algebraic degree of F is defined as the minimum of degrees of all nonzero linear
combinations of the component functions of F , namely,
m
d e g (F ) = min d e g ( τj f j (x )). (4.12)
m∗
τ∈ 2 j =1
The two measures defined above in terms of linear combinations of the component func-
tions obviously make the design of cryptographically strong vectorial Boolean functions
much harder than in the Boolean case. In certain situations one may use additional al-
gebraic structures in those cases such structures are available, but usually one prefer to
involve the structure of finite fields and to consider mappings F over 2n so that isomor-
phically F : n → n is equivalent to F : 2n → 2n (once the basis of the finite field is
2 2
fixed).
Example 4.4.1 Consider the mapping F over 2n , for n odd, given as a polynomial F (x ) =
x 3, thus 2n x → x 3 ∈ 2n . Since gcd(3, 2n ) = 1 for odd k , F is a permutation. Further-
more, NF = 2n −1 − 2 n −1 which is exceptionally high nonlinearity and such functions are
2
called almost bent (AB) for this reason. The mapping x 2k +1 is also known as Gold map-
ping, when gcd(k , n) = 1.
Another important property of substitution boxes is their differential table. Actually, this
property of having low uniformity of differentials is of the same importance as nonlin-
earity in the design of S-boxes since it leads to differential cryptanalysis which is one of
the most powerful cryptanalytic tools.
Definition 4.4.2 Let F be an (n, m ) S-box, that is F : n → m . For any a ∈ n and b ∈ m,
2 2
we denote
δF (a ,b ) = #{x ∈ n , F (Xn + a ) + F (Xn ) = b } (4.13)
where #S is the cardinality of any set S. We define
δ(F ) = max n δF (a ,b ). (4.14)
a =0,b ∈
The smaller the δ(F ), the better the differential properties of F .
The above definition is more generally stated in terms of vector space mappings, since
when m n where is no corresponding finite field representation. In the Boolean case,
when m = 1, the above differentials are commonly denoted as Da,f (x ) = f (x + a ) + f (x ),
which is a derivative of f in direction a = 0, and obviously Da,f (x ) ∈ n .
Exercise 4.4.3 Show that if deg( f ) = d then deg(Da,f ) ≤ d − 1.
The algebraic degree of F is defined as the minimum of degrees of all nonzero linear
combinations of the component functions of F , namely,
m
d e g (F ) = min d e g ( τj f j (x )). (4.12)
m∗
τ∈ 2 j =1
The two measures defined above in terms of linear combinations of the component func-
tions obviously make the design of cryptographically strong vectorial Boolean functions
much harder than in the Boolean case. In certain situations one may use additional al-
gebraic structures in those cases such structures are available, but usually one prefer to
involve the structure of finite fields and to consider mappings F over 2n so that isomor-
phically F : n → n is equivalent to F : 2n → 2n (once the basis of the finite field is
2 2
fixed).
Example 4.4.1 Consider the mapping F over 2n , for n odd, given as a polynomial F (x ) =
x 3, thus 2n x → x 3 ∈ 2n . Since gcd(3, 2n ) = 1 for odd k , F is a permutation. Further-
more, NF = 2n −1 − 2 n −1 which is exceptionally high nonlinearity and such functions are
2
called almost bent (AB) for this reason. The mapping x 2k +1 is also known as Gold map-
ping, when gcd(k , n) = 1.
Another important property of substitution boxes is their differential table. Actually, this
property of having low uniformity of differentials is of the same importance as nonlin-
earity in the design of S-boxes since it leads to differential cryptanalysis which is one of
the most powerful cryptanalytic tools.
Definition 4.4.2 Let F be an (n, m ) S-box, that is F : n → m . For any a ∈ n and b ∈ m,
2 2
we denote
δF (a ,b ) = #{x ∈ n , F (Xn + a ) + F (Xn ) = b } (4.13)
where #S is the cardinality of any set S. We define
δ(F ) = max n δF (a ,b ). (4.14)
a =0,b ∈
The smaller the δ(F ), the better the differential properties of F .
The above definition is more generally stated in terms of vector space mappings, since
when m n where is no corresponding finite field representation. In the Boolean case,
when m = 1, the above differentials are commonly denoted as Da,f (x ) = f (x + a ) + f (x ),
which is a derivative of f in direction a = 0, and obviously Da,f (x ) ∈ n .
Exercise 4.4.3 Show that if deg( f ) = d then deg(Da,f ) ≤ d − 1.
