arXiv:1710.02034v2 [] 16 Feb 2018

Simpler proof for nonlinearity of majority function
Thomas W. Cusick

∗

Department of Mathematics, University at Buffalo, Buffalo, NY
14260, USA

Abstract
Given a Boolean function f , the (Hamming) weight wt(f ) and the
nonlinearity N (f ) are well known to be important in designing functions that are useful in cryptography. The nonlinearity is expensive to
compute, in general, so any formulas giving the nonlinearity for particular functions f are significant. The well known majority function
has been extensively studied in a cryptographic context for the last
dozen years or so, and there is a formula for its nonlinearity. The
known proofs for this formula rely on many detailed results for the
Krawtchouk polynomials. This paper gives a much simpler proof.

Key words: Hamming weight, nonlinearity, Boolean functions, majority
function, Walsh transform.
Mathematics Subject Classifications (2010) 94C10 94A60 06E30

1

Introduction

Boolean functions have many applications, particularly in coding theory
and cryptography. A detailed account of the latter applications can be
found in the book [4]. If we define Vn to be the vector space of dimension
n over the finite field GF (2) = {0, 1}, then an n variable Boolean function
f (x1 , x2 , ..., xn ) = f (x) is a map from Vn to GF (2). Every Boolean function
f (x) has a unique polynomial representation (usually called the algebraic
normal form [4, p. 8]), and the degree of f is the degree of this polynomial.
A function of degree at most 1 is called affine, and if the constant term is
0 such a function is called linear. We let Bn denote the set of all Boolean
∗

Email: cusick@buffalo.edu

1

functions in n variables, with addition and multiplication done mod 2. If
we list the 2n elements of Vn as v0 = (0, ..., 0), v1 = (0, ..., 0, 1), ... in lexicographic order (we abbreviate this as lexico order below), then the 2n -vector
(f (v0 ), f (v1 ), . . . , f (v2n −1 )) is called the truth table of f. The weight (also
called Hamming weight) wt(f ) of f is defined to be the number of 1′ s in
the truth table for f . In many cryptographic uses of Boolean functions, it
is important that the truth table of each function f has an equal number of
0′ s and 1′ s; in that case, we say that the function f is balanced.
The distance d(f, g) between two Boolean functions f and g in the same
number of variables is defined by
d(f, g) = wt(f + g),
where the polynomial addition is done mod 2. An important concept in
cryptography is the nonlinearity N (f ) defined by
N (f ) = min d(f, a) .
a af f ine

In order for a Boolean function to be useful in a cryptographic application, it
is usually necessary that the function has high nonlinearity (see, for example,
[4, p. 122]). So-called Fourier analysis of Boolean functions (see [4, Chapter
2]) is very important in cryptography and other contexts. The efficient
computation of values of the nonlinearity is important here, and for this a
very important tool is the Walsh transform of a Boolean function fn in n
variables. The Walsh transform of fn is the map Wf : Vn → R defined by
X
(−1)f (x)+w·x ,
Wf (w) =
x∈Vn

where the values of f = fn are taken to be the real numbers 0 and 1. This
Walsh transform has also been important in physics and other sciences for
at least 40 years. In this paper we want the Walsh transform because of the
well known formula (see [4, Th. 2.21, p. 17], where fˆ is used instead of f )
N (fn ) = 2n−1 −

1
max |Wf (u)|.
2 u∈Vn

We shall use the obvious fact
Wf (0) = 2n − 2wt(f )
without comment in the rest of the paper.
2

(1)

2

Weight = nonlinearity if weight is small enough

It follows from the definitions that the nonlinearity is always ≤ the weight.
The following lemma gives a useful sufficient condition for the weight and
nonlinearity to be equal. This lemma is well known to experts, but I have
not found a statement of it in the literature. The proof below was shown
to me by Claude Carlet; it is much simpler than the proof using the Walsh
transform given in [3], which is a preliminary version of this paper. Before
[3] was written, this lemma was stated in a version of [7].
Lemma 1. Suppose f is a Boolean function in n variables with wt(f ) ≤
2n−2 . Then wt(f ) = N (f ).
Proof. We give a proof by contradiction. Suppose a is an affine function
such that
d(a, f ) < wt(f ) ≤ 2n−2 .
Then a is not constant and by the triangle inequality (0 is the zero function)
wt(a) = d(a, 0) ≤ d(a, f ) + d(f, 0) < 2n−2 + 2n−2 = 2n−1 .
This is a contradiction since the nonconstant affine function a is balanced,
and so has weight 2n−1 .
Lemma 1 is sharp in the sense that it is no longer true if we replace the
upper bound on wt(f ) by 2n−2 + 1. For example, the function with n = 3
having truth table (0, 0, 0, 1, 0, 0, 1, 1) (its algebraic normal form is x1 x2 x3 +
x1 x2 + x2 x3 ) has weight 3 and nonlinearity 1. However, sometimes we can
use Lemma 1 to evaluate the nonlinearity of functions gn in n variables even
if wt(gn ) 6= N (gn ), and even if wt(gn ) > 2n−2 . An example of this (Theorem
6) is given in the next section.

3

Finding nonlinearity of the majority function

The Boolean majority function Mk (x) can be defined in several slightly
different ways, but here we use the most common one, namely
Mk (x) = 1 if and only if wt(x) ≥ k/2.
The majority function seems to have been first mentioned in a cryptographic
context in the 1991 book [8, pp. 70-80], where only the case of k odd was
considered. The function has been of special interest in cryptography for
3

the last dozen years or so because this function and variants of it can be
proven to have optimal algebraic immunity. We do not need to explain this
technical concept here; interested readers can find a discussion of it in [4, pp.
174-176]. A useful recent survey of the applications of majority functions
to algebraic immunity is given in [2]. The papers [1, 6, 9, 11, 12, 13] and
others referenced in those papers all contain recent work on cryptographic
applications of these functions. It is necessary to know the nonlinearity of
the majority function to begin such studies.
A frequently quoted determination of the nonlinearity of the majority
function was given in [6, Th. 3, p. 52], using many detailed results on the
Krawtchouk polynomials (these date back to 1929; see [10, pp. 150-154] for
a study of these polynomials and proofs of some of their properties). It is
convenient to deal with the cases of odd and even k separately, so we define:
M2n+1 (x) = 1 if and only if wt(x) ≥ n + 1

(2)

M2n (x) = 1 if and only if wt(x) ≥ n.

(3)

and
For any k, we let M (k) denote the truth table of Mk (x). We let A(k) and
B(k) denote, respectively, the left and right halves of the truth table, so
M (k) = A(k)B(k)
(juxtaposition of the truth tables, each one being thought of simply as a
bitstring). We give a much simpler proof for the value of the nonlinearity of
the majority function in Theorem 5 below, but first we need three preliminary lemmas. We use the notation C(f ) for the complement of f, that is,
the function obtained by switching 0 to 1 and 1 to 0 for every entry in the
truth table of f. Similarly, if S is a bitstring, then C(S) is its complement.
Also, S ∗ denotes the bitstring S in reverse order.
Lemma 2. We have M (2n + 1) = C(M (2n))∗ M (2n) for n ≥ 2.
Proof. By (2), we can describe the two halves of M (2n + 1) by
A(2n + 1) = {0y : wt(y) ≥ n + 1, y in lexico order}

(4)

B(2n + 1) = {1y : wt(y) ≥ n, y in lexico order}.

(5)

and
Now (4) implies
A(2n + 1)∗ = {0y : wt(y) ≥ n + 1, y in reverse lexico order},
4

so (5) gives
B(2n + 1) = C(A(2n + 1))∗ .

(6)

It follows from (3) and (4) that
A(2n + 1) = {C(1y) : wt(y) ≤ n, y in lexico order}
= {C(y1) : wt(y) ≤ n, y in reverse lexico order}
= C(M (2n))∗
and then (6) gives B(2n + 1) = M (2n).
Below is an example, in which we use the notation ai for a string of i
symbols a = 0 or 1.
Example 1. M (5) = 07 103 1013 03 1013 017
Note that it follows from (4) and (6) that wt(M (2n + 1)) = 22n , so
M2n+1 (x) is a balanced function.
Lemma 3. For any truth table A, the nonlinearity of the function with truth
table A C(A)∗ is given by
N (A C(A)∗ ) = 2N (A).
Proof. For any affine function a we have
d(A, a) = d(C(A), C(a)) = d(C(A)∗ , C(a)∗ ).
Hence the lemma follows from the fact that aC(a)∗ is an affine function
whenever a is (see the well known Folklore Lemma [4, Lemma 2.2, p. 8]).

Lemma 4. We have wt(A(2n + 1)) = 22n−1 − 21 2n
n for n ≥ 2.

Proof. If we let b2n denote a bitstring of length 2n, then (4) gives

n 
X
2n
2n
2n
wt(A(2n + 1)) = 2 − |{b2n : wt(b2n ) ≤ n}| = 2 −
j
j=0

and now the Binomial Theorem implies the formula in the lemma.
Our next example illustrates Lemmas 2 and 4.
Example 2.
M (6) = 07 103 1013 03 1013 017 03 1013 017 0115
A(7) = 015 1 07 103 1013 07 103 1013 03 1013 017
5

Now the nonlinearity formulas for Mk (x) are given in the following theorem.
Theorem 5. The nonlinearity of the majority function for n ≥ 2 is given
by
 
2n
2n
N (M (2n + 1)) = 2wt(A(2n + 1)) = 2 −
(7)
n
and

 
1
1 2n
N (M (2n)) = N (M (2n + 1)) = 22n−1 −
.
(8)
2
2 n

Proof. The value 22n − 2n
for M (2n + 1) (in a different notation) was
n
obtained via (1) in [8, Th. 4.20, p. 74]. The proof uses only elementary
properties of binomial coefficients but is long enough so that we will not
repeat it here. Now Lemma 4 completes the proof of (7). Finally, Lemmas
2 and 3 imply (8).
Note that Lemma 2 gives A(2n + 1) = C(M (2n))∗ (see Example 2) and
with (8) plus Lemma 4 we obtain
N (A(2n + 1)) = N (M (2n)) = wt(A(2n + 1),
which is a weight = nonlinearity result not implied by Lemma 1.
We can use Lemma 1 to obtain even more information about the majority
function, for example we can determine N (B(2n)), which is given in the next
theorem. The next example, which illustrates how the truth tables of M (i)
change as i increases, may be helpful in reading the proof.
Example 3.
M (2n − 1) = A(2n − 1) B(2n − 1)
M (2n)

= A(2n − 1) B(2n − 1) B(2n)

M (2n + 1) = Q1(2n + 1) M (2n − 1) M (2n − 1) B(2n)
Theorem 6. The nonlinearity of B(2n) for n ≥ 3 is equal to
∗

wt(C(B(2n)) ) = 2

2n−2
X

j=n+1

=

2n−2
X

j=n+1





 

2n − 2
2n − 2
+
j
n




2n − 2
1 2n − 2
2n−3
.
+2
−
2 n−1
j
6

(9)

(10)

Proof. Let Q1(2n+1) denote the first quarter of the truth table of M (2n+1).
It follows from Lemma 2 that
Q1(2n + 1) = C(B(2n))∗ .

(11)

If we let Q1A(2n + 1) and Q1B(2n + 1) denote, respectively, the left and
right halves of the truth table for Q1(2n + 1) and we let b2n−2 denote a
bitstring of length 2n − 2, then
Q1A(2n + 1) = {000b2n−2 : wt(b2n−2 ) ≥ n + 1, b2n−2 in lexico order}
and
Q1B(2n + 1) = {001b2n−2 : wt(b2n−2 ) ≥ n, b2n−2 in lexico order}.
Therefore
wt(Q1A(2n + 1)) =

2n−2
X

j=n+1

and
wt(Q1B(2n + 1)) =



2n−2
X
j=n


2n − 2
j

(12)


2n − 2
.
j

(13)

Now (9) follows from (11), (12) and (13), and (10) follows from (9) by
elementary properties of binomial coefficients.
Simple estimates using (10) show that wt(C(B(2n))∗ ) < 22n−2 . Hence
Lemma 1 gives wt(C(B(2n))∗ ) = N (C(B(2n))∗ ) = N (B(2n)).
The methods in Section 3 can be used to clarify various earlier results
in the literature. For example, it is easy to show that the functions φ2k
discussed in [5, p. 106] satisfy φ2k = M (2k).

References
[1] A. Braeken, B. Preneel, On the algebraic immunity of symmetric
Boolean functions, Indocrypt 2005 (Berlin: Springer LNCS 3797,
2005), 35–48. Extended version http://eprint.iacr.org/2005/245.
[2] C. Carlet: A survey on nonlinear Boolean functions with optimal
algebraic immunity suitable for stream ciphers, Vietnam J. Math.
41 (4) (2013), 527–541.

7

[3] T. W. Cusick, Weight=nonlinearity for all small weight Boolean
functions, https://arxiv.org/abs/1710.02034, 10 pp., 2017.
[4] Thomas W. Cusick, Pantelimon Stănică: Cryptographic Boolean
Functions and Applications, Second Edition, Elsevier-Academic
Press, San Diego, 2017.
[5] D. K. Dalai, K. C. Gupta, S. Maitra: Cryptographically significant
Boolean functions: construction and analysis in terms of algebraic
immunity, Fast Software Encryption (FSE 2005) (Berlin: Springer
LNCS 3557, 2005), 98–111.
[6] D. K. Dalai, S. Maitra, S. Sarkar: Basic theory in the construction
of Boolean functions with maximum possible algebraic immunity,
Designs, Codes Crypto. 40 (2006), 41–58.
[7] E. M. Sanger, Rotation Symmetric Boolean Functions, Ph. D. thesis,
University at Buffalo, 2017.
[8] C. Ding, G. Xiao, W. Shan: The Stability Theory of Stream Ciphers
(Berlin: Springer LNCS 561, 1991).
[9] S. Fu, C. Li, K. Matsuura, L. Qu: Construction of rotation symmetric Boolean functions with maximum algebraic immunity, Cryptology
and Network Security (CANS 2009) (Berlin: Springer LNCS 5888,
2009), 402–412.
[10] F. J. McWilliams and N. J. A. Sloane, The Theory of ErrorCorrecting codes, North Holland, Amsterdam, 1978.
[11] S. Sarkar, S. Maitra: Construction of rotation symmetric Boolean
functions with optimal algebraic immunity, Proceedings of Applied Algebra, Algebraic Algorithms and Error-Correcting Codes
(AAECC–17) (Berlin: Springer LNCS 4851, 2007), 271–280.
[12] S. Su: Construction of balanced even-variable Boolean functions on
odd number of variables with maximum algebraic immunity, Internat. J. Computer Math. 92 (2015), 2219–2232.
[13] S. Su, X. Tang: Construction of rotation symmetric Boolean functions with optimal algebraic immunity and high nonlinearity, Designs, Codes Crypto. 71 (2014), 183–199.

8

