Page 153 - 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. 153
s Pasalic: Symmetric Key Cryptography and its Relation to Graph Theory 141
{u ∈ L : u 2k +1 = 1} be the cyclic subgroup of L of order 2k + 1, which is essentially
the group of (2k + 1)th primitive roots of unity. Then, α2k −1 = β is a generator of ,
and = {αs (2k −1), s = 0, . . . , 2k }, where α ∈ L is a primitive element. Now, any ele-
ment x ∈ L∗ can be uniquely represented as x = γu , where γ ∈ K ∗ and u ∈ , and
furthermore ∪u ∈ u K ∗ = L∗. For convenience, we denote P(x ) = t ai x i (2k −1) so that
i =1
F (x ) = Trkn (P(x )). The following result specify three equivalent necessary and sufficient
conditions (we only state two here) for F to be vectorial bent [7].
Theorem 4.5.1 Let n = 2k , and define F (x ) = Trkn (P(x )), where P(x ) = t =1 a i x i (2k −1)
i
and t ≤ 2k . Then the following conditions are equivalent:
1. F is a vectorial bent function of dimension k .
2. u ∈ (−1)Tr1k (λF (u )) = 1 for all λ ∈ K ∗.
3. There are two values u ∈ such that F (u ) = 0, and furthermore if F (u 0) = 0, then
F is one-to-one and onto from 0 = \ u 0 to K .
The proof is rather tedious but relies on the nice property of the exponents (known as
Dillon exponent) of the terms x i (2k −1). Indeed, since x ∈ G F (2n ) can be written as x = u y
for u ∈ U , y ∈ G F (2k ), then F (u y ) = t =1 a i (u y )i (2k −1) = t =1 a i u i (2k −1) = F (u ), as
i i
y i (2k −1) = 1 for any y because y ∈ K ∗. This means that F is constant on any coset u K ∗
which makes the analysis much easier.
Exercise 4.5.2 (Semi-hard) Show the item (2) above by using the fact that F is vectorial
bent if and only if WF (λ, σ) = ±2k for any λ ∈ K ∗ and any σ ∈ L. Here, WF (λ, σ) =
x ∈L(−1)Tr1k (λF (x ))+Tr1k (σx ). Use the representation x = u γ for the elements in L∗, and that
F (u γ) = F (u ) for any γ ∈ K ∗. Thus WF (λ, σ) can be therefore written (using F (0) = 0) as
1 + u ∈U γ∈K ∗ (−1)Tr1k (λF (u γ))+Tr1k (σu γ) ...
We conclude this part by mentioning that there exist various generalizations of the con-
cept of bent functions, for instance one may naturally define F : n → n , for prime
p p
p = 2, but this requires a modification of the main cryptographic notions.
4.6 Graph theoretic aspects of Boolean functions
Let G be a multiplicative group of order v . A k -subset D of G is a (v, k , λ, µ) partial dif-
ference set (PDS) if each non-identity element in D can be represented as g h−1 (g , h ∈
D, g = h) in exactly λ ways, and each non-identity element in G \ D can be represented
as g h−1 (g , h ∈ D, g = h) in exactly µ ways. We shall always assume that the identity
element 1G of G is not contained in D. Using the language of group ring algebra R[G ],
{u ∈ L : u 2k +1 = 1} be the cyclic subgroup of L of order 2k + 1, which is essentially
the group of (2k + 1)th primitive roots of unity. Then, α2k −1 = β is a generator of ,
and = {αs (2k −1), s = 0, . . . , 2k }, where α ∈ L is a primitive element. Now, any ele-
ment x ∈ L∗ can be uniquely represented as x = γu , where γ ∈ K ∗ and u ∈ , and
furthermore ∪u ∈ u K ∗ = L∗. For convenience, we denote P(x ) = t ai x i (2k −1) so that
i =1
F (x ) = Trkn (P(x )). The following result specify three equivalent necessary and sufficient
conditions (we only state two here) for F to be vectorial bent [7].
Theorem 4.5.1 Let n = 2k , and define F (x ) = Trkn (P(x )), where P(x ) = t =1 a i x i (2k −1)
i
and t ≤ 2k . Then the following conditions are equivalent:
1. F is a vectorial bent function of dimension k .
2. u ∈ (−1)Tr1k (λF (u )) = 1 for all λ ∈ K ∗.
3. There are two values u ∈ such that F (u ) = 0, and furthermore if F (u 0) = 0, then
F is one-to-one and onto from 0 = \ u 0 to K .
The proof is rather tedious but relies on the nice property of the exponents (known as
Dillon exponent) of the terms x i (2k −1). Indeed, since x ∈ G F (2n ) can be written as x = u y
for u ∈ U , y ∈ G F (2k ), then F (u y ) = t =1 a i (u y )i (2k −1) = t =1 a i u i (2k −1) = F (u ), as
i i
y i (2k −1) = 1 for any y because y ∈ K ∗. This means that F is constant on any coset u K ∗
which makes the analysis much easier.
Exercise 4.5.2 (Semi-hard) Show the item (2) above by using the fact that F is vectorial
bent if and only if WF (λ, σ) = ±2k for any λ ∈ K ∗ and any σ ∈ L. Here, WF (λ, σ) =
x ∈L(−1)Tr1k (λF (x ))+Tr1k (σx ). Use the representation x = u γ for the elements in L∗, and that
F (u γ) = F (u ) for any γ ∈ K ∗. Thus WF (λ, σ) can be therefore written (using F (0) = 0) as
1 + u ∈U γ∈K ∗ (−1)Tr1k (λF (u γ))+Tr1k (σu γ) ...
We conclude this part by mentioning that there exist various generalizations of the con-
cept of bent functions, for instance one may naturally define F : n → n , for prime
p p
p = 2, but this requires a modification of the main cryptographic notions.
4.6 Graph theoretic aspects of Boolean functions
Let G be a multiplicative group of order v . A k -subset D of G is a (v, k , λ, µ) partial dif-
ference set (PDS) if each non-identity element in D can be represented as g h−1 (g , h ∈
D, g = h) in exactly λ ways, and each non-identity element in G \ D can be represented
as g h−1 (g , h ∈ D, g = h) in exactly µ ways. We shall always assume that the identity
element 1G of G is not contained in D. Using the language of group ring algebra R[G ],
