Page 155 - 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. 155
s Pasalic: Symmetric Key Cryptography and its Relation to Graph Theory 143
counting argument shows that D(D −d −1) = e (v −D −1). Notice that in general strongly
regular graphs appear to be difficult to investigate.
The adjacency matrix A f of size 2n × 2n is the matrix whose entries are Ai ,j = f (ui ⊕
uj ), thus Ai ,j = 1 if and only if ui and uj are connected. Given a graph Γf and its ad-
jacency matrix A f the spectrum Sp e c (Γf ) is the set of eigenvalues of A f . The following
result specifies the eigenvalues in terms of Walsh coefficients and vice versa.
Theorem 4.6.2 Let f : n → 2, and let λi , 0 ≤ i ≤ 2n − 1 be the eigenvalues of its associ-
2
ated graph Γf . Then λi = Wf (bi ), for any i .
PROOF. The eigenvectors of the Cayley graph Γf are the characters Qw(x ) = (−1)w·x of
n . Moreover, the i -th eigenvalue of Af , corresponding to the eigenvector Qbi is given by
2
λi = x∈ n (−1)bi ·x f (x ) = Wf (bi ).
2
It is known that a connected r -regular graph is strongly regular if and only if it has
exactly three distinct eigenvalues λ0 = r (or λ0 = D in our notation) and λ1, λ2. Further-
more, we have the following e = r + λ1λ2 + λ1 + λ2 and d = r + λ1λ2. It can be shown that
bent functions, thus n is even, are the only Boolean functions whose associated Cayley
graph is a strongly regular graph with e = d . In particular, for bent functions we have
λ2 = −λ1 = 2n/2−1 and λ0 = D = 2n−1 ± 2n/2−1.
Exercise 4.6.3 For n = 4 verify that f (x1, . . . , x4) = x1x2 +x3x4 is a bent function. Compute
the parameters e = d .
An additional property of bent functions is related to the notion of the triangle-free
property. In other words, a graph is triangle-free if there are no paths of the form x y z x ,
where the vertices x , y , z are distinct. It can be shown that if Γf is triangle-free then f
cannot be bent. But this property cannot be used for distinguishing the bent property
of Boolean functions since the converse is not true. That is, there are functions whose
graphs contain (many) triangles but they are not bent.
4.7 References
[1] C. Carlet, Boolean Functions for Cryptography and Error Correcting Codes. Cam-
bridge University Press, 2010.
[2] J. Dillon, APN polynomials: An update. In Fq9, the 9th International Conference on
Finite Fields and Applications, 2009.
[3] J. F. Dillon, Elementary Haddamard Difference Sets. Ph. D. thesis, University of
Maryland, U.S.A., 1974.
[4] F. J. MacWilliams and N. J. A. Sloane, T he Theory of Error-Correcting Codes. North-
Holland, Amsterdam, 1977.
counting argument shows that D(D −d −1) = e (v −D −1). Notice that in general strongly
regular graphs appear to be difficult to investigate.
The adjacency matrix A f of size 2n × 2n is the matrix whose entries are Ai ,j = f (ui ⊕
uj ), thus Ai ,j = 1 if and only if ui and uj are connected. Given a graph Γf and its ad-
jacency matrix A f the spectrum Sp e c (Γf ) is the set of eigenvalues of A f . The following
result specifies the eigenvalues in terms of Walsh coefficients and vice versa.
Theorem 4.6.2 Let f : n → 2, and let λi , 0 ≤ i ≤ 2n − 1 be the eigenvalues of its associ-
2
ated graph Γf . Then λi = Wf (bi ), for any i .
PROOF. The eigenvectors of the Cayley graph Γf are the characters Qw(x ) = (−1)w·x of
n . Moreover, the i -th eigenvalue of Af , corresponding to the eigenvector Qbi is given by
2
λi = x∈ n (−1)bi ·x f (x ) = Wf (bi ).
2
It is known that a connected r -regular graph is strongly regular if and only if it has
exactly three distinct eigenvalues λ0 = r (or λ0 = D in our notation) and λ1, λ2. Further-
more, we have the following e = r + λ1λ2 + λ1 + λ2 and d = r + λ1λ2. It can be shown that
bent functions, thus n is even, are the only Boolean functions whose associated Cayley
graph is a strongly regular graph with e = d . In particular, for bent functions we have
λ2 = −λ1 = 2n/2−1 and λ0 = D = 2n−1 ± 2n/2−1.
Exercise 4.6.3 For n = 4 verify that f (x1, . . . , x4) = x1x2 +x3x4 is a bent function. Compute
the parameters e = d .
An additional property of bent functions is related to the notion of the triangle-free
property. In other words, a graph is triangle-free if there are no paths of the form x y z x ,
where the vertices x , y , z are distinct. It can be shown that if Γf is triangle-free then f
cannot be bent. But this property cannot be used for distinguishing the bent property
of Boolean functions since the converse is not true. That is, there are functions whose
graphs contain (many) triangles but they are not bent.
4.7 References
[1] C. Carlet, Boolean Functions for Cryptography and Error Correcting Codes. Cam-
bridge University Press, 2010.
[2] J. Dillon, APN polynomials: An update. In Fq9, the 9th International Conference on
Finite Fields and Applications, 2009.
[3] J. F. Dillon, Elementary Haddamard Difference Sets. Ph. D. thesis, University of
Maryland, U.S.A., 1974.
[4] F. J. MacWilliams and N. J. A. Sloane, T he Theory of Error-Correcting Codes. North-
Holland, Amsterdam, 1977.
