arXiv:1708.09313v1 [cs.IT] 30 Aug 2017

Rotation Symmetric Bent Boolean Functions for
n = 2p
T. W. Cusick
University at Buffalo, 244 Math. Bldg. Buffalo, NY 14260
Corresponding author- e-mail: cusick@buffalo.edu
E. M. Sanger
University at Buffalo, 244 Math. Bldg., Buffalo, NY 14260
e-mail: ellynsan@buffalo.edu
Abstract
It has been conjectured that there are no homogeneous rotation
symmetric bent Boolean functions of degree greater than two. In this
paper we begin by proving that sums of short-cycle rotation symmetric
bent Boolean functions must contain a specific degree two monomial
rotation symmetric Boolean function. We then prove most cases of the
conjecture in n = 2p, p > 2 prime, variables and extend this work to
the nonhomogeneous case.

1

Introduction

A Boolean function in n variables can be defined as a map from Vn , the
n-dimensional vector space over the two element field F2 , to F2 . If f is a
Boolean function in n variables, the truth table of f is defined to be the 2n tuple given by (f (v0 ), f (v1 ), . . . , f (v2n −1 )) where v0 = (0, . . . , 0, 0), v1 =
(0, . . . , 0, 1), . . . , v2n −1 = (1, . . . , 1, 1) are the 2n elements of Vn listed in
lexicographical order. The weight or Hamming weight of f (notation wt(f ))
is the number of 1’s that appear in the truth table of f .
As described in [1, pp. 5-6], every Boolean function on Vn can be expressed as a polynomial over F2 in n binary variables by:
X
an−1
f (x0 , . . . , xn−1 ) =
ca xa00 · · · xn−1
a∈Vn

where ca ∈ F2 and a = (a0 , . . . , an−1 ) with each ai equal to 0 or 1. The
above representation is the algebraic normal form (ANF) of f . Let di be the
1

number of variables in the i-th monomial of f , so di is the algebraic degree
(or just the degree) of the monomial. If we let D be the set of the distinct
degrees of the monomials in f which have non-zero coefficients, then the
degree (notation deg(f )) of f is given by max(D). If D contains only one element, then each monomial in f has the same degree and f is homogeneous.
If deg(f ) = 1, then f is affine, and if f is affine and homogeneous (i.e. the
constant term is 0), then f is linear.
A Boolean function f is rotation symmetric (RotS) if its ANF is invariant
under any power of the cyclic permutation ρ(x0 , . . . , xn−1 ) = (x1 , . . . , xn−1 , x0 ).
We will use the notation u ∼ v to indicate that there exists some 1 ≤ k ≤ n
such that ρk (u) = v. Clearly ∼ defines an equivalence relation on Vn .
Let On (x) denote the orbit of x under the action of ρk , 1 ≤ k ≤ n, and
let Gn be the set of representatives of all the orbits in Vn . Then a rotation
symmetric Boolean function f can be written as
a0 ⊕ a1 x 0 ⊕

n−1
X

a1j x0 xj ⊕ . . . ⊕ a12...n x0 x1 · · · xn−1 ,

j=1

where the coefficients a0 , a1 , a1j , . . . , a12...n ∈ F2 , and the existence of a
representative term x0 xi2 · · · xil implies the existence of all the terms from
On (x0 , xi2 , . . . , xil ) in the algebraic normal form. We call this representation
the short algebraic normal form (SANF) of f .
Unless otherwise specified, all subscripts in any monomial will be taken
mod (n) with entries in {0, 1, . . . , n − 1}. We may omit the modulus if it is
clear from the context.
Suppose f has SANF x0 xi1 . . . xil , then we say f is a monomial rotation
symmetric (MRS) function and call it full-cycle if |On (x0 , xi1 , . . . , xil )| =
n. Thus if f is full-cycle then it contains n monomials in its ANF. If
|On (x0 , xi1 , . . . , xil )| < n we say f is short-cycle. In this case f will contain n/w monomials in its ANF for some divisor w > 1 of n.
The Hamming distance between two Boolean functions f and g, denoted
d(f, g), is defined as d(f, g) = wt(f ⊕ g). Each Boolean function f has an
associated sign function, fˆ : R∗ → C∗ , defined by fˆ(x) = (−1)f (x) .
Definition 1.1. The Walsh transform of a function f : Vn → F2 is the map
W (f ) : Vn → R given by,
X
f (x)(−1)w·x
W (f )(w) =
x∈Vn

The Walsh spectrum of f is the list of the 2n Walsh coefficients given by
W (f )(w) as w varies.
2

Definition 1.2. A matrix H is called a Hadamard matrix of order n if it is
an n × n matrix of ±1s such that
HH t = nIn ,
where H t is the transpose of H and In is the n × n identity matrix.
Definition 1.3. A Boolean function f in n variables is called bent if and
only if the Walsh transform coefficients of fˆ are all ±2n/2 .
Definition 1.4. The nonlinearity of a function f, denoted by Nf , is defined
by
Nf = min d(f, g),
g∈An

where An is the set of all affine functions on Vn .
From [1, pp. 76-77] we have the following equivalent definition of the
bent property:
Theorem 1.1. Let f : Vn → F2 be a Boolean function. Then the following
are equivalent:
(i) f is bent.
(ii) Mfˆ = (fˆ(u ⊕ v)) is a Hadamard matrix.
(iii) The nonlinearity of f is Nf = 2n−1 − 2n/2−1 .
It is easy to observe that bent functions exist only for even dimensions.
Let n be even and v = (a0 , a1 , . . . , an−1 ); then we will use the notation
v′ = (a0 , . . . , a n2 −1 ) and v′′ = (a n2 , . . . , an−1 ).
Lemma 1.2. For n = 2, the degree of a bent function on V2 is 2. For
n > 2, the degree of a bent function is at most n/2.
Proof. The proof of this can be found in [1, pp. 80].

2

Rotation symmetric bent functions when n=2m

In this section we will consider rotation symmetric functions of any even
degree n. We will first prove that any degree 2 rotation symmetric bent
n/2−1
L
function must contain f0 =
xi x n2 +i and then extend this to the case
i=0

where f is composed of short-cycle MRS functions. We begin by proving
the well known fact that f0 is bent.
3

Lemma 2.1. Let n = 2m and f0 =

m−1
L

xi xm+i . Then wt(f0 ) = 22m−1 −

i=0

2m−1 and f0 is bent.

Proof. The fact that f is bent follows from [1, Cor. 5.23, p. 82], after a
permutation of the variables. Then a computation gives the weight.
To prove that any degree 2 rotation symmetric bent function, f , must
contain f0 , we will look at the matrix M = (fˆ(vi ⊕ vj ))(fˆ(vi ⊕ vj ))T to
determine when (fˆ(vi ⊕ vj )) is a Hadamard matrix. We will first simplify
the matrix M to a useful form.
Lemma 2.2. Let M = (fˆ(vi ⊕ vj ))(fˆ(vi ⊕ vj ))T where f is a Boolean
function in n variables, then
Mi,j =

n −1
2X

fˆ(vi ⊕ vk )fˆ(vk ⊕ vj ).

(1)

k=0

Proof. Let A = (fˆ(vi ⊕ vj )). Notice AT = A, so M = AA. Then
Mi,j = (AA)i,j =

n −1
2X

Aik Akj =

n −1
2X

fˆ(vi ⊕ vk )fˆ(vk ⊕ vj ).

k=0

k=0

Lemma 2.3. We have vi ∼ vj if and only if there exists k, 1 ≤ k ≤ n such
that 2k i ≡ j mod (2n − 1).
Proof. Let vi = (a0 , a1 , ..., an−2 , an−1 ), so i =

n
X

an−u 2u−1 . ⇒: Assume

u=1

vi ∼ vj , then there exists ρl , 1 ≤ l ≤ n, such that

ρl (vi ) = (ρl (a0 ), . . . , ρl (an−2 ), ρl (an−1 )) = (al , . . . , al+n−2 , al+n−1 ) = vj .

4

Thus, j =

n
X

al+n−u 2u−1 where 1 ≤ l ≤ n and

u=1

2l i =

n
X

an−u 2l+u−1

u=1

= an−1 2l + . . . + an−(n−l) 2l+(n−l)−1 + an−(n−l+1) 2l+(n−l+1)−1 +
an−(n−l+2) 2l+(n−l+2)−1 + . . . + a0 2l+n−1
= an−1 2l + . . . + al 2n−1 + al−1 2n + al−2 2n+1 . . . + a0 2n−1+l
≡ al−1 + al−2 2 + . . . + al 2n−1 mod (2n − 1)
≡ al+n−1 + al+n−2 2 + . . . + al+1 2n−2 + al 2n−1 mod (2n − 1)
≡ j mod (2n − 1),
since indices are taken mod n.
Thus there exists k, 1 ≤ k ≤ n such that 2k i ≡j mod (2n − 1).
⇐: Assume there exists k, 1 ≤ k ≤ n such that 2k i ≡ j mod (2n − 1).
Then
2k i =

n
X

an−u 2k+u−1

u=1

= an−1 2k + . . . + an−(n−k) 2k+(n−k)−1 + an−(n−k+1) 2k+(n−k+1)−1
+an−(n−k+2) 2k+(n−k+2)−1 + . . . + a0 2n−1+k
= an−1 2k + . . . + ak 2n−1 + ak−1 2n + ak−2 2n+1 + . . . + a0 2n−1+k
≡ ak−1 + ak−2 2 + . . . + ak 2n−1

mod (2n − 1)

= j.
Thus vj = (ak−1 , ak−2 , . . . , ak ) so ρk−1 (vi ) = vj and vi ∼ vj .
Lemma 2.4. We have va ∼ vb if and only if v2n −1−a ∼ v2n −1−b .
Proof. By Lemma 2.3,
va ∼ vb

⇐⇒

there exists k, 1 ≤ k ≤ n such that 2k a ≡ b mod (2n − 1)

⇐⇒

2n − 1 − 2k a ≡ 2n − 1 − b

⇐⇒

2k (2n − 1 − a) ≡ 2n − 1 − b

⇐⇒

v2n −1−a ∼ v2n −1−b .

5

Lemma 2.5.
M0,2n −1 =

2n−1
X−1

2fˆ(vk )fˆ(v2n −1−k ).

(2)

k=0

Proof. From (1) we have,
M0,2n −1 =

n −1
2X

fˆ(v0 ⊕ vk )fˆ(vk ⊕ v2n −1 ) =

n −1
2X

fˆ(vk )fˆ(v2n −1−k )

k=0

k=0

= fˆ(v0 )fˆ(v2n −1 ) + fˆ(v1 )fˆ(v2n −2 ) + . . . + fˆ(v2n−1 −1 )fˆ(v2n−1 )
+fˆ(v2n−1 )fˆ(v2n−1 −1 ) + . . . + fˆ(v2n −2 )fˆ(v1 ) + fˆ(v2n −1 )fˆ(v0 )
=

2n−1
X−1

2fˆ(vk )fˆ(v2n −1−k ).

k=0

Lemma 2.6. The function f0 =

m−1
L

xi xm+i is the only MRS short-cycle

i=0

function of degree 2 in n = 2m variables.
Proof. Let f be an MRS function with SANF x0 xk . Suppose f is short-cycle,
then f has 1 ≤ M < 2m monomials and
f = x0 xk ⊕ x1 xk+1 ⊕ . . . ⊕ xM −1 xk+M −1 .
Thus {0, k} = {M, k + M }. Since 1 ≤ M < 2m = n then we have the
following cases:
(i) 0 = M and k ≡ M + k mod (n). This is a contradiction since 1 ≤ M .
(ii) k = M and 0 ≡ M + k mod (n). Thus 0 ≡ M + k mod (n) ≡
2M mod (2m). So 2M = 2am for some a ∈ Z. Since 1 ≤ M < 2m,
then 2 ≤ 2am < 4m and so a = 1. Thus M = m.
Thus f is a short-cycle if and only if k = m which gives f = f0 .
We now have enough to prove that f0 is the only homogeneous MRS
bent function of degree 2:
Theorem 2.7. Let f be a rotation symmetric boolean function in n = 2m
variables which has the SANF x0 xk . Then f is bent if and only if k = m.

6

Proof. Assume k 6= m = n2 . Then by Lemma 2.6, f is full cycle and we write
n−1
L
f=
xi xk+i . Then each variable xi , 0 ≤ i ≤ n − 1, appears in two distinct
i=0

monomials in f and there are n (even) monomials in f . We will first show
f (vi ) = f (v2n −1−i ), 0 ≤ i ≤ n − 1, and hence fˆ(vi ) = fˆ(v2n −1−i ). Notice
f (vi ) = 0 when there are an even number of monomials in f which have a
value of 1 and f (vi ) = 1 when there are an odd number of monomials which
have a value of 1.
Fix i = I and let wt(vI ) = l. Suppose f (vI ) has r, s, and t monomials
of the form xj xh with {xj , xh } = {1, 1}, {1, 0}, and {0, 0} respectively, so
f (vI ) ≡ r mod 2. Since each variable xi appears in two distinct monomials
of f , then by counting the number of times xi = 1 in f we see 2r+s = 2l and
s must be even. Also, we know there are n monomials in f so r + s + t = n.
Clearly f (vI ) = 0 ⇐⇒ r is even ⇐⇒ t is even, since s, n are both even
and r + s + t = n. It is easy to see that f (v2n −1−I ) = f (v¯I ) ≡ t mod 2.
Thus f (v2n −1−I ) = 0 ⇐⇒ t is even.
Hence for any i, 0 ≤ i ≤ 2n − 1, we have f (vi ) = f (v2n −1−i ) and
therefore fˆ(vi ) = fˆ(v2n −1−i ). So (2) becomes:
M0,2n −1 =

2n−1
X−1

2(fˆ(vi ))2 = 2n .

i=0

Thus if k 6= m then M0,2n −1 6= 0 and we have that (fˆ(vi ⊕ vj )) is not
Hadamard. Thus by Theorem 1.1 f is not bent. The remainder of the
theorem follows from Lemma 2.1.
Corollary 2.8. If n = 2m, then any degree 2 rotation symmetric bent
m−1
L
function must contain f0 =
xi xm+i .
i=0

Proof. Assume f is a rotation symmetric function of degree 2. By [1, Th.
5.29, p. 83] we can assume f has only quadratic monomials, so f has SANF
n−1
L
ai x0 xi where the coefficients ai ∈ F2 . Let gk be the function with SANF
i=1

ak x0 xk where 1 ≤ k ≤ n − 1. Suppose f does not contain f0 , then a n2 = 0.
n−1
L
We have gk = ak
xi xk+i when 1 ≤ k ≤ n − 1 and from the proof of
i=0

Theorem 2.7, since an/2 = 0 we know gˆk (vi ) = gˆk (v2n −1−i ) for 1 ≤ i ≤ n−1.
\
n−1
n−1
n−1
n−1
Q
Q
Q
L
gˆk (v2n −1−i ) =
gˆk (vi ) =
gˆk . Thus fˆ(vi ) =
gk =
Also, fˆ =
k=1

k=1

k=1

7

k=1

fˆ(v2n −1−i ). So (2) gives:
M0,2n −1 =

2n−1
X−1

2(fˆ(vk ))2 = 2n .

k=0

Thus M0,2n −1 6= 0, so (fˆ(vi ⊕ vj )) is not Hadamard and therefore by Theorem 1.1 f is not bent.
Necessary and sufficient conditions for a bent quadratic function are
given in [6, Lemma 1, p. 4909]. The Lemma gives an alternate proof of
Corollary 2.8 as discussed in [6, Rmk. 1, p. 4910]. A characterization of
any bent RS function of degree 2 follows from [4, Th. 3.7, p. 6]. Examples
show that [4, Th. 3.1, p. 3] is false.
L
We will now look at rotation symmetric functions f =
fi of any degree
i

where each of the fi is a short-cycle MRS Boolean function. We will prove
that f is bent only if fi = f0 for some i. To do this we need the following
result from [5, pp. 218].
Theorem 2.9. Let f be a function on Vn and J ⊂ {0, 1, 2, . . . , n − 1} such
that f does not contain any term xj1 · · · xjt where t > 1 and j1 , . . . , jt ∈ J.
Then the nonlinearity of f satisfies Nf ≤ 2n−1 − 2s−1 , where s = |J|.
Theorem 2.10. Let n = 2m, then f0 =

m−1
L

xi xm+i is the only bent short-

i=0

cycle MRS Boolean function in n variables.

Proof. Let f have SANF x0 xa1 · · · xad−1 and suppose f is a short-cycle function. Then the number of monomials in f is k where 1 ≤ k < 2m. Thus,
f = x0 xa1 · · · xad−1 ⊕ x1 xa1 +1 · · · xad−1 +1 ⊕ · · · ⊕ xk−1 xa1 +k−1 · · · xad−1 +k−1
It is easy to see then that {0, a1 , . . . , ad−1 } = {k, a1 + k, . . . , ad−1 + k} =
. . . = {lk, a1 + lk, . . . , ad−1 + lk} where lk < 2m. By Lemma 3.1 we know
k must divide n = 2m, thus 1 ≤ k ≤ m. Thus by rotation symmetry
the tuple {ai , ai + k, . . . , ai + lk} appears in each monomial of f , for every
i, 0 ≤ i ≤ d − 1. If k = m then l = 1 and f has SANF
f = x0 xa1 xa2 . . . xag−1 xm xm+a1 . . . xm+ag−1 ,

(3)

where 0 < a1 < a2 < . . . < ag−1 < m. First consider g > 1. Suppose
ak < m and ak + 1 = m; then m + ak < 2m and m + ak + 1 = 2m. So
8

if xak +1 = xm then xm+ak +1 = x0 . Thus for each monomial in f, g of the
variables xi have i < m and g have i ≥ m. Let J = {m − 1, m, . . . , n − 1}.
Thus by Theorem 2.9 we have Nf ≤ 2n−1 − 2m < 2n−1 − 2m−1 , so f is not
bent by Theorem 1.1. If g = 1 then f = f0 which we know is bent. Thus if
k = m then f is bent only if f = f0 . If k < m then by regrouping the terms
we have that,
f=

k−1
M

xi xb1 +i · · · xbg +i xk+i xb1 +k+i · · · xbg +k+i · · · xlk+i xb1 +lk+i · · · xbg +lk+i

i=0

From the first term in the monomial, xi , we see that each monomial contains
at least one element of the set {x0 , x1 , . . . , xk−1 }. Since k < m then k − 1 <
m − 1. So if we let J = {m − 1, m, m + 1, . . . , n − 1}, then by Theorem 2.9
we have Nf ≤ 2n−1 − 2m < 2n−1 − 2m−1 . Thus f is not bent by Theorem
1.1.
Theorem 2.11. Let n =
L2m and let f in n variables be a sum of MRS shortcycle functions, so f =
fi , where each fi has fewer than n monomials. If
i

f is bent then one of the fi is f0 =

m−1
L

xi xm+i .

i=0

Proof. Assume f is bent and no fi is f0 . Then any short-cycle of the form
in equation (3) has g > 1 and from the proof of Theorem 2.10 we see that
each monomial in f contains at least one variable xi where i < m − 1.
Thus if we let J = {m − 1, m, . . . , n − 1} then f does not contain any
term xj1 · · · xjt where t > 1 and ji ∈ J; hence from Theorem 2.9 we have
Nf ≤ 2n−1 − 2m < 2n−1 − 2m−1 . Thus f cannot be bent, contradiction.
Therefore one of the fi is f0 .

3

Homogeneous rotation symmetric bent functions
when n=2p

Using ideas similar to those in section 2, we can prove that the only homogeneous MRS bent function in n = 2p variables, where p > 2 is prime, is
p−1
L
f0 =
xi xp+i . By a different method, this result was proven for any n by
i=0

Meng et al. [3, Th. 11, pp. 1114]
Notice we have already proven this for some cases in section 2. For the
remainder of the cases we must first further simplify (2). To do this we will
need a few facts about the rotation symmetric equivalence classes of Vn .
9

Lemma 3.1. |On (vi )| divides n.
Proof. On (vi ) is the orbit generated by vi ∈ Vn under the action of G
where G is the group of left cyclic shifts. Thus |On (vi )| = |G : Gvi |, where
Gvi = {ρ ∈ G|ρ(vi ) = vi }. Since |G| = n then |On (vi )| divides n.
Lemma 3.2. |On (vi )| = 2 ⇐⇒ vi ∼ v 2n −1 .
3

Proof. ⇒: |On (vi )| = 2 ⇐⇒ On (vi ) = {(1, 0, 1, 0, . . . , 1, 0), (0, 1, 0, 1, . . . , 0, 1)}.
Let vi = (0, 1, 0, 1, . . . , 0, 1) ⇒ i = 1 + 22 + 24 + . . . + 2n−2 ⇒
3i = (1 + 2)i = (1 + 2)(1 + 22 + 24 + . . . + 2n−2 )
= (1 + 22 + 24 + . . . + 2n−2 ) + (2 + 23 + 25 + . . . + 2n−1 )
= 1 + 2 + 22 + 23 + 24 + . . . + 2n−1
n

⇒ v3i = v2n −1 since v2n −1 = (1, 1, 1, . . . , 1). So we have i = 2 3−1 . Since
(0, 1, 0, 1, . . . , 0, 1) ∼ (1, 0, 1, 0, . . . , 1, 0) we have (1, 0, 1, 0, . . . , 1, 0) ∼ v 2n −1 .
3
⇐: Reverse the argument used above.

M0,2n −1

n
2

is an odd prime, then
X
fˆ(vk )fˆ(v2n −1−k )
= 2 + 2fˆ(v0 )fˆ(v2n −1 ) + 2n

Theorem 3.3. If n is even and

vk ∈Gn
|On (vk )|=n
vk ≁v2n −1−k

+n

X

fˆ(vk )fˆ(v2n −1−k ) + n

vk ∈Gn
|On (vk )|= n
2

X

(fˆ(vk ))2 . (4)

vk ∈Gn
|On (vk )|=n
vk ∼v2n −1−k

Proof. Let n = 2p where p is an odd prime. Then by Lemma 3.1, |On (vi )| =
1, 2, p, or n.
Let vi ∈ Vn such that |On (vi )| = 1, then vi = v0 or v2n −1 which appears
as the first term of (2) with k = 0.
n
n
If |On (vi )| = 2 then vi = v 2n −1 and 2n − 1 − 2 3−1 = 2 2 3−1 , so vi ∼
3
v2n −1−i and we have one 2(fˆ(v 2n −1 )2 term. Since fˆ(vi ) = ±1 for any
3

n
vi ∈ Vn then (fˆ(vi ))2 = 1 for any vi . So when k = 2 3−1 in (2), then
2fˆ(vk )fˆ(v2n −1−k ) = 2.
Now suppose vi = (a0 , a1 , . . . , an−1 ) ∈ Gn and |On (vi )| = p, then
vi′ = vi′′ . So to consider the cyclic shifts of vi we need only consider the cyclic
shifts of (a0 , a1 , . . . , ap−1 ). Notice v2n −1−i = (1 + a0 , 1 + a1 , . . . , 1 + an−1 )
and we have (1 + a0 , 1 + a1 , . . . , 1 + ap−1 ) = (1 + ap , 1 + ap+1 , . . . , 1 + an−1 )

10

so |On (v2n −1−i )| = p as well. Since p is odd (1 + a0 , 1 + a1 , . . . , 1 + ap−1 ) will
have a different number of 1’s than (a0 , a1 , . . . , ap−1 ). Hence vi ≁ v2n −1−i
since (a0 , a1 , . . . , ap−1 ) ≁ (1+a0 , 1+a1 , . . . , 1+ap−1 ). Thus from Lemma 2.4,
if |On (vi )| = p, then grouping the corresponding terms in (2) by the equivalence class representatives gives 2pfˆ(vi )fˆ(v2n −1−i ) = nfˆ(vi )fˆ(v2n −1−i ).
If |On (vi )| = n and vi ≁ v2n −1−i then grouping the corresponding terms
in (2) by the equivalence class representative gives the new coefficient 2n. If
vi ∼ v2n −1−i then this coefficient becomes 2 n2 = n.
Thus (2) reduces to the above equation.
Lemma 3.4. Let n = 2p, where p > 2 is prime. If f is a rotation symmetric
bent Boolean function in n variables, then fˆ(v0 ) = −fˆ(v2n −1 ).
Proof. From Theorem 1.1 f is bent if and only if M = 2n I2n . Thus if f is
bent then M0,2n −1 = 0. From (4) we see that in order for M0,2n −1 to be 0
we need the 2 which appears from the case vk = v 2n −1 to cancel. Let
3

X

a = fˆ(v0 )fˆ(v2n −1 ), b =

fˆ(vk )fˆ(v2n −1−k ),

vk ∈Gn
|On (vk )|=n
vk ≁v2n −1−k

c=

X

fˆ(vk )fˆ(v2n −1−k ), and d =

vk ∈Gn
|On (vk )|= n
2

X

(fˆ(vk ))2 .

vk ∈Gn
|On (vk )|=n
vk ∼v2n −1−k

Assume f is bent, then (4) becomes:
2 + 2a + 4pb + 2pc + 2pd = 0 ⇒ p(2b + c + d) = −1 − a.
If a = 1, then p(2b + c + d) = −2. Since p > 2 and 2b + c + d ∈ Z
this is a contradiction. Thus a = −1 and fˆ(v0 )fˆ(v2n −1 ) = −1. Therefore
fˆ(v0 ) = −fˆ(v2n −1 ) since fˆ(vi ) = ±1 for all i.
The following corollary now proves that full-cycle homogeneous MRS
Boolean functions in 2p variables cannot be bent.
Corollary 3.5. Let n = 2p where p is an odd prime. Let f be an MRS
boolean function with SANF x0 xa1 xa2 . . . xad−1 . If the number of monomials
in f is n, then f is not bent.
Proof. Using Theorem 1.1 we need only show M0,2n −1 6= 0. If the number
of monomials in f is n, then we have fˆ(v0 ) = fˆ(v2n −1 ) since n = 2p is even.
Thus M0,2n −1 6= 0 so f is not bent.
11

We can now prove that f0 is the only homogeneous MRS bent function.
Theorem 3.6. Let n = 2p, where p > 2 is prime. The only bent homogep−1
L
neous MRS Boolean function in n variables is f0 =
xi xp+i .
i=0

Proof. Any monomial homogeneous rotation symmetric function, f , has
SANF x0 xa1 . . . xad−1 and is either short-cycle or full-cycle. If f is fullcycle then from Corollary 3.5 f is not bent. If f is short-cycle then from
Theorem 2.10, f is bent if and only if f = f0 .
Theorem 3.7. Let n = 2p, where p > 2 is prime, and let f be a rotation
symmetric Boolean function in n variables with SANF x0 xa1 · · · xad−1 . If f
has p monomials, then d is even and f has SANF given by equation (3).
Proof. If the number of monomials in f is p then
f = x0 xa1 · · · xad−1 ⊕ x1 xa1 +1 · · · xad−1 +1 ⊕ · · · ⊕ xp−1 xa1 +p−1 · · · xad−1 +p−1
Thus {0, a1 , . . . , aad−1 } = {p, a1 + p, . . . , ad−1 + p} so each pair {xai , xai +p }
appears in every monomial and f is of the form in (3). The result that d is
even follows immediately since each monomial contains the pairs {xai , xai +p }.
Theorem 3.8. Let n = 2p, where p > 2 is prime. Let f =

s
L

fi where

i=1

each fi has SANF x0 xai1 · · · xaid−1 and deg(f ) = d. Let r be the number of
fi that are short-cycle and l be the number of fi that are long-cycle. If f is
bent then d is even. Furthermore, if d = 2 then f contains f0 and if d 6= 2
then r ≥ 1 is odd and l ≥ 1.
Proof. Let f = f1 ⊕ f2 ⊕ · · · ⊕ fs where each fi has SANF x0 xai1 . . . xaid−1 .
Thus deg(fi ) = d ∀i and so deg(f ) = d. Since n = 2p then GCD(n, d) =
1, 2, p, or n and from Lemma 3.1 we know that the number of monomials in
each fi is either 1, 2, p, or n.
(i) Suppose the number of monomials in fi for some i is 1, then since fi
is rotation symmetric then fi = x0 x1 . . . xn−1 and d = n.
(ii) Suppose the number of monomials in fi for some i is 2, then f =
x0 xai1 . . . xaid−1 ⊕ x1 xai1 +1 . . . xaid−1 +1 . It is easy to see by induction
that the first monomial contains all of the even indices and the second
monomial contains all of the odd indices. Thus d = p.
12

(iii) Suppose the number of monomials in fi for some i is p, then from
Theorem 3.7 fi is of the form in equation (3) and d is even.
Thus fi is a short-cycle function only if d = p, n, or is even. Let GCD(n, d) =
1, then the number of monomials in fi is n for all i. Thus, fˆi (v0 ) =
fˆi (v2n −1 ) ∀i and so fˆ(v0 ) = fˆ(v2n −1 ) and by Lemma 3.4 f is not bent.
If GCD(n, d) = p then fi either has 2 monomials or n monomials for each
i. Thus fˆ(v0 ) = fˆ(v2n −1 ) and so f is not bent. If GCD(n, d) = n then
d = n and f is not bent by Lemma 1.2. Now suppose GCD(n, d) = 2, thus
d is even. If d = 2 then by Corollary 2.8 f must contain f0 which is the
only degree 2 short-cycle. If d 6= 2 then by (iii), the short-cycle functions of
degree d are of the form in equation (3). By Theorem 2.11 we know that
any combination of these short-cycle functions is not bent, thus f must also
contain a long-cycle and so l ≥ 1. If r is even then,
fˆ(v0 ) =

s
Y

fˆi (v0 ) = (−1)r

s
Y

fˆi (v2n −1 ) = fˆ(v2n −1 )

i=1

i=1

since fˆi (v0 ) = −fˆi (v2n −1 ) when fi is short-cycle and fˆi (v0 ) = fˆi (v2n −1 )
when fi is long-cycle. Thus by Lemma 3.4 f is not bent.
Remark. The previous Theorem says that any homogeneous RotS bent
function must have even degree and contain an odd number of short-cycle
MRS functions. If the degree is greater than 2 then it must also contain at
least one long-cycle MRS function.
Lemma 3.9. Let n = 2p, p an odd prime, and f be a homogeneous RotS
Boolean function in n variables with deg(f ) = d = 2k where k > 1. Let
s
l
L
L
f =
fi ⊕
fi where for all 1 ≤ i ≤ s, fi is an MRS short-cycle
i=1

i=s+1

function and for all s + 1 ≤ i ≤ l, fi is an MRS full-cycle function. Suppose
fi has SANF x0 xai1 . . . xaid−1 . If 2 ≤ r ≤ d − 2 for all s + 1 ≤ i ≤ l, where
r is the number of odd indices in {ai1 , . . . , aid−1 }, then f is not bent.
Proof. Since the degree of f is even, we know from the proof of Theorem 3.8
that any short-cycle is of the form in (3). Thus no short-cycle contains a term
xj1 . . . xjt where t > 1 and j1 , . . . , jt are in the set J = {0, 2, 4, . . . , n−2, n−1}
since deg(f ) ≥ 4. If the number of odd indices, r, in the first monomial of
any full-cycle in f is 2 ≤ r ≤ d − 2, then each monomial in the full-cycles
has either r odd indices and d − r even indices or d − r odd indices and
r even indices. Since 2 ≤ r ≤ d − 2 then 2 ≤ d − r ≤ d − 2, thus each
13

monomial contains at least 2 odd indices. Thus, because J contains only
one odd number, n − 1, then no monomial, xj1 . . . xjt , in a long-cycle has
xj1 , . . . , xjt ∈ J where t > 1. Thus by Theorem 2.9, Nf ≤ 2n−1 − 2p <
2n−1 − 2p−1 and so f is not bent by Theorem 1.1.
L
Remark. Lemma 3.9 says that if f =
fi is a homogeneous RotS Boolean
i

function of even degree d, d > 2, in n = 2p variables then one of the fi must
have a monomial with exactly one odd index.
L
Let f be a homogeneous RotS function of degree d with SANF
βi ,
1≤i≤s

where βi = xk(i) xk(i) · · · xk(i) and
0

(i)

2

d−1

(i)

sj , j = 1, 2, . . . , d, by sj
(i)

(i)
k0

(i)

= 0 for all i. Define a sequence

(i)

(i)

= kj − kj−1 for 1 ≤ j ≤ d − 1, and sd =

(i)

k0 + n − kd−1 . Let sf be the largest distance between two consecutive
(i)

indices in all of the monomials in f , thus sf = max sj . Then from [3, Th.
i,j

13, pp. 1116] we have the following:
Theorem 3.10. Let f be a homogeneous RotS function with degree d ≥ 3
in n variables. If sf ≤ n2 , then f is not bent.
We can use Theorem 3.10 to get a useful bound on the degree of any
possible homogeneous RotS bent function in 2p variables:
Theorem 3.11. Let f be a homogeneous RotS bent function of degree d ≥ 3
in n = 2p variables, p an odd prime. Then d ≤ (p + 3)/2.
Proof. Suppose d > (p + 3)/2. We choose J = {0, 1, 2, 4, . . . , 2p − 2} (so
|J| = p + 1 and J has p even elements) in Theorem 2.9. The theorem
applies since now no monomial x0 xa1 . . . xad−1 can have all of its variables
xj in J and also have a gap of length ≥ (n/2) + 1 in its index set (necessary
for f to be bent by Theorem 3.10). Suppose the monomial x0 xa1 . . . xad−1
has all of its variables xj in J and d > p+3
2 . If there is a gap in the indices
greater than or equal to p + 1, then at least p−1
2 of the indices in J do not
p+3
appear in the monomial. Thus there are at most p + 1 − p−1
2 = 2 possible
indices in J which appear in the monomial. Thus d ≤ p+3
2 , contradiction.
Note, for example, that if the indices are 0, 1, 2, p + 3 p + 5, . . . , 2p − 2 then
| {z }
gap

we have a gap of length p + 1 but only (p + 3)/2 indices, contradicting our
assumption about d. Now Theorem 2.9 gives

14

Nf ≤ 2n−1 − 2p ≤ 2n−1 − 2n/2 < 2n−1 − 2n/2−1 ,
so f is not bent by Theorem 1.1, contradicting our hypothesis.

4

Nonhomogeneous rotation symmetric bent functions when n=2p

We have already shown in Theorem 2.11 that any bent function composed
only of short-cycle MRS functions must contain f0 .
We can now extend the ideas used in section 3 to show that in most
cases any bent rotation symmetric Boolean function in n = 2p, p > 2 prime,
variables must contain f0 .
Theorem 4.1. Let n = 2p where p is an odd prime. Let f = f1 ⊕ f2 ⊕
. . . ⊕ fs be a rotation symmetric Boolean function where each fi has SANF
x0 aa1 . . . xadi −1 . If di = 2 or the number of monomials in each fi is either
p−1
L
2 or n, then f is bent only if f contains f0 =
xj xp+j . If f contains an
j=0

even number of fi , where the number of monomials in fi is p and all other
fi contain 2 or n monomials, then f is not bent.
Proof. Let f = f1 ⊕ f2 ⊕ . . . ⊕ fs where for each fi , di = 2 or the number
of monomials in fi is 2 or n. Suppose f is bent and does not contain f0 .
Then since f0 is the only short-cycle RotS function with degree 2 then each
fi contains either 2 or n monomials. Thus from the proof of Corollary 3.5,
fˆi (v0 ) = fˆi (v2n −1 ) for all i. Thus
Y
Y
fˆ(v0 ) =
fˆi (v0 ) =
fˆi (v2n −1 ) = fˆ(v2n −1 )
and from Lemma 3.4 we see that f cannot be bent which is a contradiction.
Thus f must contain f0 .
Now suppose the number of monomials in f1 , f2 , . . . , f2r is p and
f2r+1 , f2r+2 , . . . , fs contain either 2 or n monomials. Then fˆi (v0 ) = −fˆi (v2n −1 )
for 1 ≤ i ≤ 2r and fˆi (v0 ) = fˆ(v2n −1 ) for 2r + 1 ≤ i ≤ s. Thus,
fˆ(v0 ) =

s
Y

fˆi (v0 ) =

i=1

2r
Y

−fˆi (v2n −1 )

s
Y
i=2r+1

i=1

= fˆ(v2n −1 ).
Thus from Lemma 3.4, f cannot be bent.
15

fˆi (v2n −1 ) = (−1)2r fˆ(v2n −1 )

Remark. If fi has 1 monomial, for some i, then deg(fi ) = n. Thus deg(f ) =
n and so f is not bent from Lemma 1.2.
Remark. The previous Theorem says that any nonhomogeneous RotS bent
function must contain an odd number of short-cycle MRS functions of even
degree and at least one function which is a long-cycle MRS function.

References
[1] T. W. Cusick and P. Stănică, Cryptographic Boolean Functions and
Applications (San Diego: Academic Press, 2009).
[2] H. Kim, S-M. Park and S. G. Hahn, On the weight and nonlinearity of homogeneous rotation symmetric Boolean functions of degree 2,
Discrete Applied Mathematics 157, 428-432 (2009)
[3] Q. Meng, L. Chen, F.-W. Fu, On homogeneous rotation symmetric bent
functions, Discrete Appl. Math. 158 (2010), 1111–1117.
[4] X. Zhang, G. Gao, On the conjecture about the nonexistence of rotation
symmetric bent functions, arXiv.org, arXiv:1303.2282v1, 7 pp. (2013).
[5] Y. Zheng, X-M. Zhang, H. Imai, Restriction, terms and nonlinearity of
Boolean functions, Theoretical Computer Science 226, 207-223 (1999)
[6] Guangpu Gao, Xiyong Zhang, Wenfen Liu, and Claude Carlet, Constructions of Quadratic and Cubic Rotation Symmetric Bent Functions,
IEEE Transactions on Information Theory 58, 4908-4913 (2012)

16

