# Bent functions and strongly regular graphs

Valentino Smaldore 111<EMAIL_ADDRESS>Dipartimento di
Matematica, Informatica ed Economia, Università degli Studi della Basilicata,
Viale dell’Ateneo Lucano 10, 85100 Potenza, Italy 222Dipartimento di Tecnica e
Gestione dei Sistemi Industriali, Università degli Studi di Padova, Stradella
S. Nicola 3, 36100 Vicenza, Italy.

###### Abstract

The family of bent functions is a known class of Boolean functions, which have
a great importance in cryptography. The Cayley graph defined on
$\mathbb{Z}_{2}^{n}$ by the support of a bent function is a strongly regular
graph $srg(v,k\lambda,\mu)$, with $\lambda=\mu$. In this note we list the
parameters of such Cayley graphs. Moreover, it is given a condition on
$(n,m)$-bent functions $F=(f_{1},\ldots,f_{m})$, involving the support of
their components $f_{i}$, and their $n$-ary symmetric differences.

##  1 Introduction

A cryptosystem is an encryption and decryption algorithm for a message. If
Alice wants to send a message $p$ to Bob, the encryption algorithm $E$
computes the cyphertext $z$ starting from a key $K_{A}$, i.e. $z=E(p,K_{A})$.
Bob uses the decryption algorithm $D$ to recover $p$ from a key $K_{B}$, i.e.
$p=D(z,K_{B})$. Of necessity, for all $p,K_{A},K_{B}$,
$D(E(p,K_{A}),K_{B})=p$. Cryptosystems are called private key, if the parties
know each other and have shared informations about their private keys, or
public key if it is not necessary that the two parties know each other, and
they have two public keys. The best known private key algorithms are $DES$
(Data Encryption System) and its successor $AES$ (Advanced Encryption System).
The reader can find more information on cryptography in [11]. One of the most
importand features for cryptographic algorithms is the confusion, i.e. the
relation between any bit and all the plaintext appearing random. After the
linear cryptanalysis techniques of A. Matsui [10], one of the research item in
cryptograph was to find functions as far as possible from the linear
functions, i.e. maximizing the Hamming distance, in order to resist to linear
attacks, see [3]. Among the family of Boolean functions, such functions are
called bent functions. In [1, 2] it is given a characterization of bent
functions in terms of strongly regular graphs. Here, we give considerations on
parameters of such strongly regular graphs, and a firs characterization of
$(n,m)$-bent functions.

##  2 Preliminaries

Let $\mathbb{Z}_{2}$ be the binary field. A Boolean function is a function
$f:\mathbb{Z}_{2}^{n}\longrightarrow\mathbb{Z}_{2}$ and to denote $f$ we will
use two different notations: the classical notation, where the input string is
given by $n$ binary variables, and the $2^{n}$-tuple vector representation
$f=(f_{0}f_{1}\ldots f_{2^{n}-1})$ where $f_{i}=f(b(i))$ and $b(i)$ is the
binary expansion of the integer $i$. We will denote by $\Omega_{f}$ the
support of $f$, i.e.

$\Omega_{f}=\\{w\in\mathbb{Z}_{2}^{n}|f(w)\neq
0\\}=\\{w\in\mathbb{Z}_{2}^{n}|f(w)=1\\}.$

######  Definition 2.1.

  * •

Let $l$ be a Boolean function. We say that $l$ is a linear function if
$\forall x,y\in\mathbb{Z}_{2}^{n}$, $l(x+y)=l(x)+l(y)$.

  * •

Let $\phi$ be a Boolean function. We say that $\phi$ is an affine function if
it is a linear function plus a constant. We denote with $\mathcal{A}$ the set
of all affine functions

The nonlinearity of a Boolean function $f$ is the minimum Hamming distance
between $f$ and an affine function, i.e.

$Nl(f)=min_{\phi\in\mathcal{A}}|\\{x\in\mathbb{Z}_{2}^{n}|f(x)\neq\phi(x)\\}|.$

######  Definition 2.2.

A Boolean function $f$ is called bent function if
$Nl(f)=\frac{2^{n}-2^{\frac{n}{2}}}{2}$.

Here we define the Abstract Fourier Transform of a Boolean function $f$ as the
rational valued function $f^{*}$ which defines the coefficients of $f$ with
respect to the orthonormal basis of the group characters
$Q_{w}(x)=(-1)^{(w\cdot x)}$, when $\cdot$ is the standard inner product and
$w\cdot x=\sum_{i=1}^{n}x_{i}w_{i}=Tr^{n}_{1}(wx)$. Then

$f^{*}(w)=\frac{\sum_{x\in\mathbb{Z}_{2}^{n}}(-1)^{Tr^{n}_{1}(wx)}f(x)}{2^{n}}.$

Note that $f^{*}(b(0))=\frac{|\Omega_{f}|}{2^{n}}$. The Walsh spectrum is the
set of values of $f^{*}(w)$. Here we investigate the spectrum in terms of a
graph eigenvalue problem.

##  3 The Cayley graph $Cay(\mathbb{Z}_{2}^{n},\Omega_{f})$

######  Definition 3.1.

Let $\Gamma$ be a group with identity $e$.

  * •

A Cayley subset, is a subset $C\subseteq\Gamma$ such that $e\notin C$ and
whenever $g\in C$, then $g^{-1}\in C$.

  * •

The Cayley graph $G=Cay(\Gamma,C)$ of $\Gamma$ with respect to $C$ is the
graph whose vertex set is $\Gamma$, when two vertices $g$ and $h$ are adjacent
if and only if $gh^{-1}\in C$.

We modify this definition by dropping the condition $e\notin C$, allowing
loops in the Cayley graph.

Consider now the additive group $(\mathbb{Z}_{2}^{n},\oplus)$, where $\oplus$
is the componentwise sum. For all $w\in\mathbb{Z}_{2}^{n}$, $w^{-1}=w$, then
each subset of $\mathbb{Z}_{2}^{n}$ is a Cayley subset. We can associate each
Boolean function $f$ to the Cayley graph
$G_{f}=Cay(\mathbb{Z}_{2}^{n},\Omega_{f})$. The vertex-set $V(G_{f})$ is the
whole $\mathbb{Z}_{2}^{n}$, while the edge-set is
$E(G_{f})=\\{(u,v)\in\mathbb{Z}_{2}^{n}|u\oplus
v\in\Omega_{f}\\}=\\{(u,v)\in\mathbb{Z}_{2}^{n}|f(u\oplus v)=1\\}$. The graph
has $2^{n-dim\langle\Omega_{f}\rangle}$ which are the cosets of
$\langle\Omega_{f}\rangle$ in $\mathbb{Z}_{2}^{n}$. Since eigenvectors of the
Cayley graph are exactly the group characters
$Q_{w}(x)=(-1)^{Tr^{n}_{m}(wx)}$, see [13],the following two results give a
characterization of the spectrum of $G_{f}$ from the Walsh spectrum of $f$.

######  Result 3.2.

[1, Theorem 1] The $i$-th eigenvalue $\lambda_{i}$ of the Cayley graph, which
corresponds to the eigenvector $Q_{b(i)}$, is given by

$\lambda_{i}=\sum_{x\in\mathbb{Z}_{2}^{n}}(-1)^{Tr^{n}_{1}(b(i)x)}f(x)=2^{n}f^{*}(b(i)).$

######  Result 3.3.

[1, Proposition 2]

  1. 1.

The largest spectral coefficients is
$\lambda_{0}=2^{n}f^{*}(b(0))=|\Omega_{f}|$, with multiplicity
$2^{n-dim\langle\Omega_{f}\rangle}$.

  2. 2.

The number of non zero spectral coefficients is the rank of the adjacency
matrix of $G_{f}$.

  3. 3.

If $G_{f}$ is connected, $f$ has a spectral coefficient equal to
$-\lambda_{0}$ if and only if its Walsh spectrum is symmetric with respect to
0.

##  4 Strongly regular graphs

A strongly regular graph with parameters $(v,k,\lambda,\mu)$, denoted by
$srg(v,k,\lambda,\mu)$, is a graph with $v$ vertices, each vertex lies on $k$
edges, any two adjacent vertices have $\lambda$ common neighbours and any two
non-adjacent vertices have $\mu$ common neighbours. We give now some folklore
results on strongly regular graphs, see [4] for more details.

######  Result 4.1.

$k(k-\lambda-1)=\mu(v-k-1)$.

The spectrum of the adjacency matrix of an $srg(v,k,\lambda,\mu)$ is fully
determined by its parameters.

######  Result 4.2.

A strongly regular graph $G$ with parameters $(v,k,\lambda,\mu)$ has exactly
three eigenvalues: $k$, $\theta_{1}$ and $\theta_{2}$ of multiplicity,
respectively, $1$, $m_{1}$ and $m_{2}$, where:

$\theta_{1}=\frac{1}{2}\big{[}(\lambda-\mu)+\sqrt{(\lambda-\mu)^{2}+4(k-\mu)}\big{]},$
$\theta_{2}=\frac{1}{2}\big{[}(\lambda-\mu)-\sqrt{(\lambda-\mu)^{2}+4(k-\mu)}\big{]},$
$m_{1}=\frac{1}{2}\Big{[}(v-1)-\frac{2k-(v-1)(\lambda-\mu)}{\sqrt{(\lambda-\mu)^{2}+4(k-\mu)}}\Big{]},$
$m_{2}=\frac{1}{2}\Big{[}(v-1)+\frac{2k-(v-1)(\lambda-\mu)}{\sqrt{(\lambda-\mu)^{2}+4(k-\mu)}}\Big{]}.$

We write the spectrum as $k,\theta_{1}^{m_{1}},\theta_{2}^{m_{2}}$. On the
other hand, we can express the parameters of a strongly regular graph starting
from its spectrum

$v=1+m_{1}\theta_{1}+m_{2}\theta_{2},$
$\lambda=k+\theta_{1}\theta_{2}+\theta_{1}+\theta_{2},$
$\mu=k+\theta_{1}\theta_{2}=\lambda-\theta_{1}-\theta_{2},$

######  Corollary 4.3.

Consider a $srg(v,k,\lambda,\mu)$, with spectrum
$k,\theta_{1}^{m_{1}},\theta_{2}^{m_{2}}$. Then $\lambda=\mu$ if and only if
$\theta_{1}=-\theta_{2}$.

######  Result 4.4.

The parameters $\lambda$ and $\mu$ of a $srg(v,k,\lambda,\mu)$ may be derived
from its spectrum, since:

$\begin{cases}\lambda=k+\theta_{1}+\theta_{2}+\theta_{1}\theta_{2}\\\
\mu=k+\theta_{1}\theta_{2}.\end{cases}$ (1)

In [1, 2] is given a characterization of bent functions in a graph theoretical
point of view.

######  Result 4.5.

[1, Lemma 12] If $f$ is a bent function, the graph $G_{f}$ is a strongly
regular graph with $\lambda=\mu$.

######  Result 4.6.

[2, Theorem 3] Bent functions are the only functions whose associated Cayley
graph $G_{f}$ is a strongly regular graph with $\lambda=\mu$.

######  Proposition 4.7.

The Cayley graph $G_{f}$ of a bent function is exactly one of the following:

  * •

$srg(2^{n},\frac{2^{n}+2^{\frac{n}{2}}}{2},\frac{2^{n}+2^{\frac{n}{2}}-2^{n-1}}{2},\frac{2^{n}+2^{\frac{n}{2}}-2^{n-1}}{2});$

  * •

$srg(2^{n},\frac{2^{n}-2^{\frac{n}{2}}}{2},\frac{2^{n}-2^{\frac{n}{2}}-2^{n-1}}{2},\frac{2^{n}-2^{\frac{n}{2}}-2^{n-1}}{2}).$

###### Proof.

From [1, Definition 4] we know the three eigenvalues
$k,\theta_{1},\theta_{2}=-\theta_{1}$ of $G_{f}$. From 4.4 we get the
parameters $\lambda$ and $\mu$, while 4.1 allows us to compute
$v=2^{n}=|\mathbb{Z}_{2}^{n}|$. ∎

######  Example 4.8.

The first strongly regular graph defined by bent functions are

$n=2$

  * •

$srg(4,3,1,1)$, i.e. the complete graph $K_{4}$.

  * •

$srg(4,1,0,0)$, i.e. a trivial strongly regular graph made of 2 disconnected
edges.

$n=4$

  * •

$srg(16,10,6,6)$.

  * •

$srg(16,10,2,2)$.

$n=6$

  * •

$srg(64,36,20,20)$.

  * •

$srg(64,28,12,12)$.

$n=8$

  * •

$srg(256,136,72,72)$.

  * •

$srg(256,120,56,56)$.

$n=10$

  * •

$srg(1024,528,272,272)$.

  * •

$srg(1024,496,240,240)$.

Note that in each case graphs are the complements of the affine polar graphs
$VO^{\mp}(2n,2)$, which is the graph arising from a quadric $Q$ in the vector
space $V=V(2n,2)$ and two points $u,v\in V$ represent adjacent vertices if and
only if $Q(u-v)=0$. Note that the quadric is elliptic or hyperbolic while we
consider the first or the second example, respectively. See the table of
strongly regular graphs in [5] for more details.

##  5 Vectorial bent function

Consider now functions
$F:\mathbb{Z}_{2}^{n}\longrightarrow\mathbb{Z}_{2}^{m}$,
$F(x_{1},\ldots,x_{n})=(f_{1},\ldots,f_{m}(x_{1},\ldots,x_{n}))$, where for
each $i$, $f_{i}:\mathbb{Z}_{2}^{n}\longrightarrow\mathbb{Z}_{2}$. The set of
affine vectorial functions $\mathcal{A}_{n,m}$ is defined as in the case
$m=1$. We can introduce two different way to express the nonlinearity of a
vectorial Boolean function:

$nl(F)=min_{v\in\mathbb{Z}_{2}^{n}\setminus\\{0\\}}Nl(F\cdot v)$ (2)
$Nl(F)=min_{\phi\in\mathcal{A}_{n,m}}|\\{x\in\mathbb{Z}_{2}^{n}|F(x)\neq\phi(x)\\}|$
(3)

######  Definition 5.1.

A $(n,m)$-bent function, or vectorial bent function, is a function
$F=(f_{1},\ldots,f_{m})$ such that $nl(F)=\frac{2^{n}-2^{\frac{n}{2}}}{2}$, or
equivalently each linear combination of $f_{1},\ldots,f_{m}$ is a bent
function.

In order to give graph based properties of $(n,m)$-bent functions we need now
to define the set operation symmetric difference, which is the equivalent of
the logical operation $XOR$.

######  Definition 5.2.

The symmetric difference between two sets $A$ and $B$ is

$A\triangle B=(A\setminus B)\cup(B\setminus A)=(A\cup B)\setminus(A\cap B).$

######  Proposition 5.3.

The power set of any set $X$ is an elementary abelian $2$-group under the
operation of symmetric difference.

###### Proof.

The symmetric difference is commutative and associative:

  * •

$A\triangle B=B\triangle A$;

  * •

$(A\triangle B)\triangle C=A\triangle(B\triangle C)$.

Moreover the empty set is the identity and each element has order two:

  * •

$A\triangle\emptyset=A$;

  * •

$A\triangle A=\emptyset$.

∎

An elementary abelian $2$-group is also called Boolean group, see [8] for more
details.

The symmetric difference of a collection of sets is made of elements contained
in an odd number of sets. The $n$-ary symmetric difference is defined as
follows;

$\bigtriangleup\mathcal{M}=\Big{\\{}a\in\bigcup\mathcal{M}\Big{|}\sharp\\{A\in
M|a\in A\\}=2k+1,k\in\mathbb{N}\Big{\\}}.$

######  Proposition 5.4.

Consider a vectorial Boolean function $F=(f_{1},\ldots,f_{m})$, with
$f_{i}:\mathbb{Z}_{2}^{n}\longrightarrow\mathbb{Z}_{2}$, and let
$\Omega_{i}=\Omega_{f(i)}$ be the support of $f_{i}$, of $i=1,\ldots,m$. If
the function $F$ is $(n,m)$-bent, then the Cayley graphs
$Cay(\mathbb{Z}_{2}^{n},\bigtriangleup_{i\in I}\Omega_{i})$ are strongly
regular with $\lambda=\mu$ for all index subset $I\subseteq[1,\ldots,m]$.

## References

  * [1] A. Bernasconi, B. Codenotti, Spectral Analysis of Boolean Functions as a Graph Eigenvalue Problem, IEEE Transactions on Computers, 1999, 48(3), pp. 345-351.
  * [2] A. Bernasconi, B. Codenotti, J. M. VanderKam, A Characterization of Bent Functions in terms of Strongly Regular Graphs, IEEE Transactions on Computers, 2001, 50(9), pp. 984-985.
  * [3] E. Biham, A. Shamir, Differential cryptanalysis of DES-like cryptosystems, Journal of Cryptology, 1991, 4, pp. 3-72.
  * [4] A. E. Brouwer, H. Van Maldeghem, Strongly Regular Graphs, Encyclopedia of Mathematics and its Applications, Cambridge University Press, 2022.
  * [5] A. E. Brouwer, Parameters of Strongly Regular Graphs, https://www.win.tue.nl/ aeb/graphs/srg/srgtab.html
  * [6] C. Carlet, C. Ding, J. Yuan, Linear codes from perfect nonlinear mappings and their secret sharing schemes, IEEE Transactions on Information Theory, 2005, 51(6), pp. 2089-2102.
  * [7] D. Dong, X. Zhang, L. Qu, S. Fu, A note on vectorial bent functions, Information Processing Letters, 2013, 113(22-24), pp. 866-870.
  * [8] P. Givant, P. Halmos, Introduction to Boolean Algebras, Springer, 2009.
  * [9] K. J. Horadam, Hadamard Matrices and Their Applications, Princeton Universtity Press, 2007.
  * [10] M. Matsui, Linear cryptanalysis method for DES cypher, EUROCRYPT93, LNCS 765, Springer, 1994, pp. 386-397.
  * [11] A. J. Menezes, P. van Oorschot, S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, Boca Raton, 1997.
  * [12] S. Mesnager, Bent Functions. Fundamentals and Results, Springer, 2016.
  * [13] P. H. Zieschang, Cayley graphs of finite groups, Journal of Algebra, 1988, 118(2), pp. 447-454.