On the nonlinearity of Boolean functions with restricted input

Abstract

Very recently, Carlet, Méaux and Rotella have studied the main cryptographic features of Boolean functions when, for a given number n of variables, the input to these functions is restricted to some subset E of $\mathbb {F}_{2}^{n}$. Their study includes the particular case when E equals the set of vectors of fixed Hamming weight, which is important in the robustness of the Boolean function involved in the FLIP stream cipher. In this paper we focus on the nonlinearity of Boolean functions with restricted input and present new results related to the analysis of this nonlinearity improving the upper bound given by Carlet et al.

1 Introduction

The cryptographic criterion of interest in this manuscript is that of nonlinearity which characterizes the distance between a Boolean function and the set of affine functions (i.e. those of algebraic degree 0 or 1) and is naturally defined using the Hamming distance. More precisely, the nonlinearity of f is the minimum distance to affine functions (in terms of Reed-Muller codes, it is equal to the minimum distance of the linear code Reed-Muller code RM(1, n) ∪ (f + RM(1, n)) where RM(1, n) denotes the Reed-Muller code of order 1 and length 2ⁿ). It can be shown that the nonlinearity of a Boolean function in n variables is upper bounded by 2^n− 1 − 2^{n/2 − 1}. In order to provide confusion, cryptographic functions must lie at large Hamming distance (in the sense, close to the maximum value 2^n− 1 − 2^{n/2 − 1}) to all affine functions, equivalently must be of a large nonlinearity (in the sense, close to the upper bound 2^n− 1 − 2^{n/2 − 1}). Boolean functions achieving maximal nonlinearity are called bent functions introduced by Rothaus [8] in 1976 but already studied by Dillon [5] since 1974. For of their own sake as interesting combinatorial objects, but also for their relations to coding theory (Reed-Muller codes), combinatorics (difference sets) and applications in cryptography (design of stream ciphers), they have attracted a lot of research for more than four decades. Two references devoted especially to bent functions and containing a complete survey on bent functions are [3, 7]. It is important to point out that bent functions can not be directly used in the filter and combiner models; in particular, they are not balanced and their algebraic degree does not exceed $\frac {n}{2}$, which make them weak against fast algebraic attacks [9] even after modifying a number of values small enough to keep good nonlinearity.

In 2016, Méaux, Journault, Standaert and Carlet [6] introduced the cipher FLIP in the context of homomorphic encryption. FLIP is one of the encryption schemes specifically designed to be combined with an homomorphic encryption scheme to improve the efficiency of somewhat homomorphic encryption frameworks. It has been shown that in the context of the FLIP cipher, the important criteria of Boolean functions are the classical ones (balancedness, nonlinearity, algebraic immunity) when, for a given number n of variables, the input to these functions is restricted to some subset E of $\mathbb {F}_{2}^{n}$. In 2017, Carlet, Méaux and Rotella [4] studied Boolean functions with restricted input and their robustness in the framework of FLIP cipher. In this manuscript, we focus on one parameter of Boolean functions: the nonlinearity with restricted input. We derive new results on the analysis of the nonlinearity with restricted input improving the upper bound given by Carlet, Méaux and Rotella. The paper is organized as follows. In Section 2, we recall some background related to Boolean functions as well as some preliminaries on the nonlinearity of Boolean functions. In Section 3, we focus ourselves on the nonlinearity of Boolean functions with restricted input. Using the moments of the Walsh transform, we first derive in Section 3.1 an upper bound on that nonlinearity (Theorem 7). Next, we push further the analysis of the power sums involved in Theorem 7 and establish a new upper bound on the nonlinearity of Boolean functions with constant weight inputs improving the results of Carlet et al. (Theorem 16).

2 Preliminaries

We denote by |I| the cardinality of a finite set I. Let n be any positive integer. In this paper, we shall denote by $\mathcal {B}_{n}$ the set of all n-variable Boolean functions over $\mathbb {F}_{2}^{n}$ [1]. Any n-variable Boolean function f (that is, a mapping from $\mathbb {F}_{2}^{n}$ to $\mathbb {F}_{2}$) admits a unique algebraic normal form (ANF), that is, a representation as a multivariate polynomial over $\mathbb {F}_{2}$:

$$\begin{array}{@{}rcl@{}} f(x_{1},\ldots,x_{n})=\bigoplus\limits_{I\subseteq \{1,{\ldots} ,n\}} a_{I}\,\prod\limits_{i\in I}{x_{i}}, \end{array} $$

where the a_I’s are in $\mathbb {F}_{2}$. The terms ${\prod }_{i\in I} {x_{i}}$ are called monomials. The algebraic degree deg(f) of a Boolean function f equals the maximum degree of those monomials whose coefficients are nonzero in its algebraic normal form. A slightly different form for the algebraic normal form is $f(x)=\bigoplus _{u\in \mathbb {F}_{2}^{n}}a_{u}x^{u}$, where $a_{u}\in \mathbb {F}_{2}$ and where $x^{u}={\prod }_{i = 1}^{n}x_{i}^{u_{i}}$. Then deg(f) equals $\displaystyle \max _{a_{u}\neq 0}\text {wt}(u)$, where wt(u) denotes the Hamming weight of u, that is, wt(u) = |{i = 1,…, n∣u_i = 1}|. Given a positive integer r, we make an abuse of notation and denote by RM(r, n) the set of all n-variable Boolean functions of algebraic degrees at most r, that is, the so-called r-th order Reed-Muller code of length 2ⁿ. We recall that RM(r, n) is a vector subspace over $\mathbb {F}_{2}$ of dimension ${\sum }_{i = 0}^{r}{\left (\begin {array}{c} n \\ i \end {array}\right )}$.

The Hamming weight wt(f) of a Boolean function is the size of its support $\{x\in \mathbb {F}_{2}^{n}\mid f(x)= 1\}$ that we denote by supp(f). The Hamming distance between two n-variable Boolean functions is the Hamming weight of f ⊕ g, that is $\text {dist}(f,g)=|{\{x\in \mathbb {F}_{2}^{n}\mid f(x)\neq g(x)\}}|$.

Definition 1 (rth-order nonlinearity)

Let f be an n-variable Boolean function. Let r be a positive integer such that r ≤ n. The r-th order nonlinearity of f is the minimum Hamming distance between f and all n-variable Boolean functions from RM(r, n). We shall denote the r-th order nonlinearity of f by nl_r(f).

We have

$$ nl_{r}(f) \,= 2^{n-1}-\frac{1}{2}\max\limits_{g\in RM(r,n)} \left\vert\sum\limits_{x\in {F_{2}^{n}}}(-1)^{f(x)+g(x)}\right\vert. $$

(1)

The first-order nonlinearity of f is simply called the nonlinearity of f and is denoted by nl(f) (instead of nl₁(f)). Clearly we have nl_r(f) = 0 if and only if f has degree at most r. So, the knowledge of the nonlinearity profile (i.e. of all the nonlinearities of orders r ≥ 1) of a Boolean function includes the knowledge of its algebraic degree. It is in fact a much more complete cryptographic parameter than the single (first-order) nonlinearity and the algebraic degree. The best known upper bound on nl_r(f) has an asymptotic version [2]:

$$\begin{array}{@{}rcl@{}} nl_{r}(f) \leq 2^{n-1} - \frac{\sqrt{15}}{2}(1+\sqrt 2)^{r-2} 2^{\frac{n}{2}} + O(n^{r-2}) \end{array} $$

for every n-variable Boolean function f.

3 Results on the nonlinearity with restricted input

3.1 An upper bound derived from power sums of Walsh transform

Let n be a positive integer. Let E be any subset of $\mathbb {F}_{2}^{n}$ and let f be any Boolean function defined over E. We define

$$\begin{array}{@{}rcl@{}} \widehat{\chi_{f,E}}(a) \,=\, \sum\limits_{x\in E}(-1)^{f(x)+a\cdot x},\quad a\in\mathbb{F}_{2}^{n}, \end{array} $$

where “⋅” denotes the standard inner product in $\mathbb {F}_{2}^{n}$. In [4], the authors have introduced the following definition of the nonlinearity of a Boolean function with restricted input:

$$\begin{array}{@{}rcl@{}} NL_{E}(f) = \frac{|E|}{2} - \frac{1}{2}\max\limits_{a\in\mathbb{F}_{2}^{n}}\vert\widehat{\chi_{f,E}}(a)\vert. \end{array} $$

Clearly, NL_E is invariant under the addition by a Boolean function g whose restriction to E is affine, that is, g(x) = γ ⋅ x + β. Indeed,

$$\begin{array}{@{}rcl@{}} \widehat{\chi_{f+g,E}} (a) &=&\! \sum\limits_{x\in E}(-1)^{f(x)+\gamma\cdot x+\beta+a\cdot x} \,=\, (-1)^{\beta}\!\sum\limits_{x\in E}(-1)^{f(x)+x\cdot(a+\gamma)} \,=\,(-1)^{\beta}\widehat{\chi_{f,E}}(a+\gamma). \end{array} $$

Thus, we have the following.

Lemma 2

Let $g:\mathbb {F}_{2}^{n}\to \mathbb {F}_{2}$ such that g(x) = γ ⋅ x + βfor every x ∈ Ewhere $\gamma \in \mathbb {F}_{2}^{n}$ and $\beta \in \mathbb {F}_{2}$. Then NL_E(f + g) = NL_E(f).

In [4], it is established the following upper bound on this nonlinearity.

Theorem 3 ([4, Proposition 6])

We have

$$\begin{array}{@{}rcl@{}} NL_{E}(f)\leq \frac{|E|}{2} - \frac{\sqrt{|E| + \lambda\,}}{2}, \end{array} $$

where

$$\begin{array}{@{}rcl@{}} \lambda=\max\limits_{F\in\mathcal F}\left\vert\underset{x+y\in F^{\perp}\setminus\{0\}}{\sum\limits_{(x,y)\in E^{2}}}(-1)^{f(x)+f(y)}\right\vert. \end{array} $$

Herein $\mathcal F$ is a family of vector spaces F for each of which there exists $v\in \mathbb {F}_{2}^{n}$ such that v ⋅ (x + y) = 1for all (x, y) ∈ E² such that x + y ∈ F^⊥∖{0}. Herein and hereafter, F^⊥ denotes the dual space of the vector space F.

Remark 4

If $E=\mathbb {F}_{2}^{n}$, Theorem 3 is the classical “covering radius bound” $2^{n-1}-2^{\frac {n}{2}-1}$ (since F^⊥ = {0}).

Remark 5

Without giving the calculation, we indicate that the theorem above is a direct consequence of the following identity where F is a vector space:

$$\begin{array}{@{}rcl@{}} \sum\limits_{a\in F}\left( \widehat{\chi_{f,E}}(a)\right)^{2} = \vert F\vert\underset{x+y \in F^{\perp}}{\sum\limits_{(x,y)\in E^{2}}} (-1)^{f(x)+f(y)}. \end{array} $$

The most important feature is that Theorem 3 does not relies on any property on E but only on the fact that we sum over a vector space.

Considering the case where F is a hyperplane (in that case, the condition of Theorem 3 is satisfied), we have the following most simple bound established in [4]:

Corollary 6

We have

$$\begin{array}{@{}rcl@{}} NL_{E}(f) \leq \frac{|E|}{2}-\frac{1}{2}\sqrt{|E| + \lambda}, \end{array} $$

where

$$\begin{array}{@{}rcl@{}} \lambda=\max\limits_{a\in\mathbb{F}_{2}^{n},\,a\not= 0}\left\vert\underset{x+y=a}{\sum\limits_{x,y\in E}}(-1)^{D_{a}f(x)}\right\vert \end{array} $$

and D _a f is the derivative of f in the direction of a whose expression is given as follows:

$$\begin{array}{@{}rcl@{}} D_{a}f(x)= f(x+a)+f(x). \end{array} $$

We are going to show that Theorem 3 is a particular case of a more general result. To this end, set

$$\begin{array}{@{}rcl@{}} S_{\ell}(f,E,F) = \sum\limits_{a\in F}\left( \widehat{\chi_{f,E}}(a)\right)^{\ell}. \end{array} $$

Observe that S_ℓ(f, E, F) = 0 if and only if $\widehat {\chi _{f,E}}$ vanishes on F when ℓ is even. Next,

$$\begin{array}{@{}rcl@{}} S_{2\ell+ 2}(f,E,F)&&=\sum\limits_{a\in F}\left( \widehat{\chi_{f,E}}(a)\right)^{2\ell+ 2}\\ &&\leq \left( \max\limits_{a\in F}\vert \widehat{\chi_{f,E}}(a)\vert\right)^{2} \sum\limits_{a\in F}\left( \widehat{\chi_{f,E}}(a)\right)^{2\ell}\\ &&= \left( \max\limits_{a\in F}\vert \widehat{\chi_{f,E}}(a)\vert\right)^{2} S_{2\ell}(f,E,F) \end{array} $$

Thus we arrive at

$$ \frac{S_{2\ell+ 2}(f,E,F)}{S_{2\ell}(f,E,F)}\leq \left( \max\limits_{a\in F}\vert \widehat{\chi_{f,E}}(a)\vert\right)^{2} $$

(2)

A direct generalization of Theorem 3 is therefore the following upper bound.

Theorem 7

Let f be a Boolean function over $\mathbb {F}_{2}^{n}$. Let F be a vectorspace of $\mathbb {F}_{2}^{n}$ such that $\widehat {\chi _{f,E}}$ does not vanish on F. Then, every positive integer ℓ,

$$ NL_{E}(f) \leq \frac{|E|}{2} - \frac{1}{2}\sqrt{\frac{S_{2\ell+ 2}(f,E,F)}{S_{2\ell}(f,E,F)}}. $$

(3)

Remark 8

With our framework, the approach of [4] corresponds to take ℓ = 0 in (2) and to consider particular subspaces F. Indeed, if ℓ = 0, one has

$$\begin{array}{@{}rcl@{}} \frac{S_{2\ell+ 2}(f,E,F)}{S_{2\ell}(f,E,F)}&=&\frac{1}{\vert F\vert}\sum\limits_{a\in F}\left( \widehat{\chi_{f,E}}(a)\right)^{2}\\&=&\sum\limits_{(x,y)\in E^{2}, x+y \in F^{\perp}} (-1)^{f(x)+f(y)}. \end{array} $$

To get the absolute value, it suffices to use Lemma 2 with f_v(x) = f(x) + v ⋅ x. According to Lemma 2, one has NL_E(f) = NL_E(f_v) On the other hand,

$$\begin{array}{@{}rcl@{}} \underset{x+y \in F^{\perp}}{\sum\limits_{(x,y)\in E^{2}}} (-1)^{f_{v}(x)+f_{v}(y)}&=&\underset{x+y \in F^{\perp}}{\sum\limits_{(x,y)\in E^{2}}} (-1)^{f(x)+f(y)+v\cdot(x+y)}\\ &=&|E| + \underset{x+y \in F^{\perp}\setminus\{0\}}{\sum\limits_{(x,y)\in E^{2}}} (-1)^{f(x)+f(y)+v\cdot(x+y)}. \end{array} $$

Now, if v is chosen such that v ⋅ (x + y) = 1 for every (x, y) ∈ E² such that x + y ∈ F^⊥, then

$$\begin{array}{@{}rcl@{}} \underset{x+y \in F^{\perp}}{\sum\limits_{(x,y)\in E^{2}}}(-1)^{f_{v}(x)+f_{v}(y)}=|E|- \underset{x+y \in F^{\perp}\setminus\{0\}}{\sum\limits_{(x,y)\in E^{2}}}(-1)^{f(x)+f(y)}. \end{array} $$

Remark 9

Another approach would have been to use the following naive upper bound:

$$ S_{2\ell}(f,E,F) \leq \vert F\vert\left( \max\limits_{a\in F}\vert \widehat{\chi_{f,E}}(a)\vert\right)^{2\ell}. $$

(4)

But it will not give a better upper bound. Indeed, using the Hölder inequality (that is, ${\sum }_{a\in F} \vert u_{a}v_{a}\vert \leq \left ({\sum }_{a\in F} \vert u_{a}\vert ^{p}\right )^{\frac {1}{p}} \left ({\sum }_{a\in F} \vert u_{a}\vert ^{q}\right )^{\frac {1}{q}}$, where $\frac {1}{p}+\frac {1}{q}= 1$) with $p=\frac {\ell + 1}{\ell }$ and q = ℓ + 1, we get

$$\begin{array}{@{}rcl@{}} S_{2\ell}(f,E,F) &=& \sum\limits_{a\in F}\left( \widehat{\chi_{f,E}}(a)\right)^{2\ell} \leq \left( \sum\limits_{a\in F}\left( \widehat{\chi_{f,E}}(a)\right)^{2\ell+ 2}\right)^{\frac{\ell}{\ell+ 1}} \left( \sum\limits_{a\in F} 1\right)^{\frac{1}{\ell+ 1}}. \end{array} $$

That implies that

$$\begin{array}{@{}rcl@{}} \vert F\vert\left( S_{2\ell+ 2}(f,E,F)\right)^{\ell} \geq \left( S_{2\ell}(f,E,F)\right)^{\ell+ 1}, \end{array} $$

that is,

$$\begin{array}{@{}rcl@{}} \frac{S_{2\ell+ 2}(f,E,F)}{S_{2\ell}(f,E,F)}\geq \left( \frac{1}{\vert F\vert} S_{2\ell}(f,E,F)\right)^{\frac{1}{\ell}}. \end{array} $$

Remark 10

An important feature of Theorem 7 is that the right-hand side is a decreasing sequence. Indeed, by the Cauchy-Schwarz inequality,

$$\begin{array}{@{}rcl@{}} \left( S_{2\ell+ 2}(f,E,F)\right)^{2} \leq S_{2\ell}(f,E,F) S_{2\ell+ 4}(f,E,F) \end{array} $$

which implies that the sequence $\left (\frac {S_{2\ell + 2}(f,E,F)}{S_{2\ell }(f,E,F)}\right )_{\ell \in {\mathbb N}^{\star }}$ is an increasing sequence. Since Theorem 3 corresponds to the case where ℓ = 0, that says that (3) may be a better upper bound than Theorem 3 for every positive integers ℓ and the particular subspaces F considered in that Theorem.

But above, it is known that $\frac {{\sum }_{i}\lambda _{i}^{k + 1}}{{\sum }_{i}{\lambda _{i}^{k}}}$ tends to maxiλ_i as k tends to infinity for any finite sequence of positive numbers λ_i. That says that, the right-hand side of (4) is a decreasing sequence which tends to $\frac {|E|}{2}-\frac {1}{2}\max _{a\in F}\vert \widehat {\chi _{f,E}}(a)\vert$ as ℓ tends to infinity.

At this stage, Theorem 7 does not give enough insight on NL_E because it does not rely on the structure of E. To understand more deeply what restricting inputs implies on the nonlinearity of a Boolean function, we shall consider particular subsets E in the sequel. But before doing this, we shall push further a bit more the analysis of the power sums S_2ℓ(f, E, F) involved in Theorem 7 in the next subsection.

3.2 Analysis of the power sums involved in Theorem 7

3.2.1 A decomposition formula

We begin with a classical calculation:

$$\begin{array}{@{}rcl@{}} S_{2\ell}(f,E,F) &=& \sum\limits_{a\in F}\sum\limits_{x_{1},\dots,x_{2\ell}\in E} (-1)^{{\sum}_{i = 1}^{2\ell}f(x_{i})+a\cdot\left( {\sum}_{i = 1}^{2\ell}x_{i}\right)} \\ &=&\sum\limits_{x_{1},\dots,x_{2\ell}\in E} (-1)^{{\sum}_{i = 1}^{2\ell}f(x_{i})}\sum\limits_{a\in F}(-1)^{a\cdot\left( {\sum}_{i = 1}^{2\ell}x_{i}\right)}\\ &=&\vert F\vert \underset{x_{1}+\cdots+x_{2\ell}\in F^{\perp}}{\sum\limits_{x_{1},\dots,x_{2\ell}\in E}} (-1)^{{\sum}_{i = 1}^{2\ell}f(x_{i})}. \end{array} $$

(5)

Let us now split the latter sum as follows

$$\begin{array}{@{}rcl@{}} S_{2\ell}(f,E,F) \!&=&\! \vert F\vert\underset{x_{1}+x_{2}, x_{3}+\cdots+x_{2\ell}\in F^{\perp}}{\sum\limits_{x_{1},\dots,x_{2\ell}\in E}} (-1)^{{\sum}_{i = 1}^{2\ell}f(x_{i})} \,+\, \vert F\vert\underset{x_{1}+\cdots+x_{2\ell}\in F^{\perp}}{\underset{x_{1}+x_{2}, x_{3}+\cdots+x_{2\ell}\not\in F^{\perp}}{\sum\limits_{x_{1},\dots,x_{2\ell}\in E}}} (\!-1)^{{\sum}_{i = 1}^{2\ell}f(x_{i})}\\ &=& \vert F\vert\left( \underset{x_{1}+x_{2}\in F^{\perp}}{\sum\limits_{x_{1},x_{2}\in E}} (-1)^{f(x_{1})+f(x_{2})}\right) \left( \underset{x_{1}+\cdots+x_{2\ell-2}\in F^{\perp}}{\sum\limits_{x_{1},\dots,x_{2\ell-2}\in E}} (-1)^{{\sum}_{i = 1}^{2\ell-2}f(x_{i})}\right)\\ && \qquad + \vert F\vert\underset{x_{1}+\cdots+x_{2\ell}\in F^{\perp}}{\underset{x_{1}+x_{2}, x_{3}+\cdots+x_{2\ell}\not\in F^{\perp}}{\sum\limits_{x_{1},\dots,x_{2\ell}\in E}}} (-1)^{{\sum}_{i = 1}^{2\ell}f(x_{i})}. \end{array} $$

(6)

We then deduce from the above calculation

Proposition 11

Let f be a Boolean function over $\mathbb {F}_{2}^{n}$. Let F be a vectorspace of $\mathbb {F}_{2}^{n}$ such that $\widehat {\chi _{f,E}}$ does not vanish on F. Let ℓ be a positive integer. Then

$$\begin{array}{@{}rcl@{}} \frac{S_{2\ell+ 2}(f,E,F)}{S_{2\ell}(f,E,F)} = \sum\limits_{u\in F^{\perp}}T_{2}(f,E,u) + R_{\ell}(f,E,F), \end{array} $$

(7)

where

$$\begin{array}{@{}rcl@{}} R_{\ell}(f,E,F) &=& \frac{\underset{u, v\not\in F^{\perp}}{\sum\limits_{u+v\in F^{\perp}}} T_{2}(f,E,u)T_{2\ell}(f,E,v)}{{\sum}_{u\in F^{\perp}}T_{2\ell}(f,E,u)}\geq 0 \end{array} $$

and

$$\begin{array}{@{}rcl@{}} T_{2\ell}(f,E,u) &=& \underset{x_{1}+\cdots+x_{2\ell}=u}{\sum\limits_{x_{1},\dots,x_{2\ell}\in E}} (-1)^{{\sum}_{i = 1}^{2\ell}f(x_{i})}. \end{array} $$

Proof

Let ℓ be a positive integer. Equation (6) implies that

$$\begin{array}{@{}rcl@{}} S_{2\ell+ 2}(f,E,F) \!\!&=&\!\!\! \left( \underset{x_{1}+x_{2}\in F^{\perp}}{\sum\limits_{x_{1},x_{2}\in E}}\! (-1)^{f(x_{1})+f(x_{2})}\!\!\right)\!\! S_{2\ell}(f,E,F) \,+\, \vert F\vert\! \underset{x_{1}+\cdots+x_{2\ell+ 2}\in F^{\perp}}{\underset{x_{1}+x_{2}, x_{3}+\cdots+x_{2\ell+ 2}\not\in F^{\perp}}{\sum\limits_{x_{1},\dots,x_{2\ell+ 2}\in E}}} \!(\!-1)^{{\sum}_{i = 1}^{2\ell}f(x_{i})}. \end{array} $$

Decomposition (7) follows then from (5) and

$$\begin{array}{@{}rcl@{}} \underset{x_{1}+\cdots+x_{2\ell+ 2}\in F^{\perp}}{\underset{x_{1}+x_{2}, x_{3}+\cdots+x_{2\ell+ 2}\not\in F^{\perp}}{\sum\limits_{x_{1},\dots,x_{2\ell+ 2}\in E}}} (-1)^{{\sum}_{i = 1}^{2\ell}f(x_{i})} &=& \underset{u, v\not\in F^{\perp}}{\sum\limits_{u+v\in F^{\perp}}}T_{2}(f,E,u)T_{2\ell}(f,E,v), \end{array} $$

where $T_{2}(f,E,u)= {\sum }_{\underset {x_{1}+x_{2}=u}{x_{1},x_{2}\in E}} (-1)^{f(x_{1})+f(x_{2})}$. Now, according to Remark 10, $\frac {S_{2\ell + 2}(f,E,F)}{S_{2\ell }(f,E,F)}\geq \frac {S_{2}(f,E,F)}{S_{0}(f,E,F)}={\sum }_{\underset {x_{1}+x_{2}\in F^{\perp }}{x_{1},x_{2}\in E}} (-1)^{f(x_{1})+f(x_{2})}$ which implies that R_ℓ(f, E, F)≥ 0. □

Remark 12

Remark 10 implies also that the sequence $(R_{\ell }(f,E,F))_{\ell \in {\mathbb N}}$ is a non-decreasing sequence. Note that the sum ${\sum }_{\underset {u, v\not \in F^{\perp }}{u+v\in F^{\perp }}}T_{2}(f,E,u)T_{2\ell }(f,E,v)$ is also nonnegative because ${\sum }_{u\in F^{\perp }}T_{2\ell }(f,E,u)=\frac {1}{\vert F\vert }S_{2\ell }(f,E,F)>0$ when $\widehat {\chi _{f,E}}$ does not vanish on F. Furthermore, if ${\sum }_{\underset {u, v\not \in F^{\perp }}{u+v\in F^{\perp }}}T_{2}(f,E,u)T_{2\ell }(f,E,v) = 0$, then we have $\frac {S_{2\ell + 2}(f,E,F)}{S_{2\ell }(f,E,F)}=\frac {S_{2}(f,E,F)}{S_{0}(f,E,F)}$. Thus, according to Remark 10, the preceding equality implies that $\frac {S_{4}(f,E,F)}{S_{2}(f,E,F)}=\frac {S_{2}(f,E,F)}{S_{0}(f,E,F)}$. Next, since equality is achieved in Cauchy-Schwarz inequality if and only the two sequences involved in the inequality are proportional, $(\widehat {\chi _{f,E}})^{2}$ is therefore constant on F. The converse is also true. Hence,

$$\underset{u, v\not\in F^{\perp}}{\sum\limits_{u+v\in F^{\perp}}}T_{2}(f,E,u)T_{2\ell}(f,E,v) = 0 \iff (\widehat{\chi_{f,E}})^{2}\text{ is constant on }F. $$

3.2.2 The case ℓ = 1

We are now going to turn our attention to the case where ℓ = 1. As in Section 3.2.1, in the sequel, F denotes a vectorspace of $\mathbb {F}_{2}^{n}$ such that $\widehat {\chi _{f,E}}$ does not vanish on F. In that case, Proposition 11 says that:

$$ \frac{S_{4}(f,E,F)}{S_{2}(f,E,F)} = \sum\limits_{u\in F^{\perp}}T_{2}(f,E,u) + \frac{{\sum}_{\underset{u, v\not\in F^{\perp}}{u+v\in F^{\perp}}}T_{2}(f,E,u)T_{2}(f,E,v)}{{\sum}_{u\in F^{\perp}}T_{2}(f,E,u)}, $$

(8)

where

$$ T_{2}(f,E,u) = \underset{x+y=u}{\sum\limits_{x,y\in E}} (-1)^{f(x)+f(y)}, $$

(9)

$$\begin{array}{@{}rcl@{}} \underset{u, v\not\in F^{\perp}}{\sum\limits_{u+v\in F^{\perp}}}T_{2}(f,E,u)T_{2}(f,E,v)\geq 0. \end{array} $$

Observe next that

$$ \sum\limits_{u\in F^{\perp}}T_{2}(f,E,u) = |E| + \sum\limits_{u\in F^{\perp}\setminus\{0\}}T_{2}(f,E,u). $$

(10)

Note that this term is involved in the upper bound stated by Theorem 3. At this stage, we observe that one should deduce from Equation (8) an upper bound on NL_E and this upper bound should be better than Theorem 3 provided that the second-term at the right-hand side is positive. Thus, we are now going to study when this term vanishes, that is, when

$$ \underset{u, v\not\in F^{\perp}}{\sum\limits_{u+v\in F^{\perp}}}T_{2}(f,E,u)T_{2}(f,E,v) = 0. $$

(11)

We have restricted ourselves to suppose that $\widehat {\chi _{f,E}}$ does not vanish on F. We therefore indicate that (11) is always true when F is a vectorspace such that $\widehat {\chi _{f,E}}$ vanishes on F according to Remark 12. We have

Proposition 13

Let n > 1 be a positive integer. Let F be a vector space of $\mathbb {F}_{2}^{n}$ and E be a subset of $\mathbb {F}_{2}^{n}$ . Let R₁(f, E, F) be defined in Proposition 11. Then R₁(f, E, F) = 0 for every hyperplane F if and only if T₂(f, E, u) = 0 for every u ≠ 0.

Proof

Clearly, if T₂(f, E, u) = 0 for every u ≠ 0, (11) holds. Suppose now that (11) holds. Every hyperplane F can be written as F = {0, γ}^⊥. Therefore, (11) rewrites as

$$\begin{array}{@{}rcl@{}} \underset{u, v\not\in\{0,\gamma\}}{\sum\limits_{u+v\in\{0,\gamma\}}} T_{2}(f,E,u)T_{2}(f,E,v)= 0. \end{array} $$

Now

$$\begin{array}{@{}rcl@{}} &&\underset{u, v\not\in\{0,\gamma\}}{\sum\limits_{u+v\in\{0,\gamma\}}} T_{2}(f,E,u)T_{2}(f,E,v)\\ &&\quad = \sum\limits_{u\not\in\{0,\gamma\}}\left( T_{2}(f,E,u)\right)^{2}+\sum\limits_{u\not\in\{0,\gamma\}}T_{2}(f,E,u)T_{2}(f,E,u+\gamma). \end{array} $$

(12)

Suppose that (12) holds for every γ ≠ 0. Then

$$\begin{array}{@{}rcl@{}} 0 &=& \sum\limits_{\gamma\not= 0}\sum\limits_{u\not\in\{0,\gamma\}}\left( T_{2}(f,E,u)\right)^{2} + \sum\limits_{\gamma\not= 0}\sum\limits_{u\not\in\{0,\gamma\}}T_{2}(f,E,u)T_{2}(f,E,u+\gamma)\\ &=& \sum\limits_{u\not= 0}\left( T_{2}(f,E,u)\right)^{2} \sum\limits_{\gamma\not\in\{0,u\}} 1 + \sum\limits_{u\not= 0} T_{2}(f,E,u) \sum\limits_{\gamma\not\in\{0,u\}}T_{2}(f,E,u+\gamma)\\ &=& (2^{n}-2) \sum\limits_{u\not= 0}\left( T_{2}(f,E,u)\right)^{2} + \sum\limits_{u\not= 0} T_{2}(f,E,u) \sum\limits_{\gamma\not\in\{0,u\}}T_{2}(f,E,\gamma)\\ &=& (2^{n}-2) \sum\limits_{u\not= 0}\left( T_{2}(f,E,u)\right)^{2} \,+\, \left( \sum\limits_{u\not= 0} T_{2}(f,E,u) \sum\limits_{\gamma\not= 0}T_{2}(f,E,\gamma) \,-\, \sum\limits_{u\not= 0}\left( T_{2}(f,E,u)\right)^{2}\!\right)\\ &=& (2^{n}-3) \sum\limits_{u\not= 0}\left( T_{2}(f,E,u)\right)^{2} + \left( \sum\limits_{u\not= 0}T_{2}(f,E,u)\right)^{2}. \end{array} $$

Hence, ${\sum }_{u\not = 0}\left (T_{2}(f,E,u)\right )^{2}= 0$ implying that T₂(f, E, u) = 0 for every u ≠ 0. □

We immediately deduce the following corollary.

Corollary 14

Let n > 1 be a positive integer. Let F be a vector space of $\mathbb {F}_{2}^{n}$ and E be a subset of $\mathbb {F}_{2}^{n}$. Let R_ℓ(f, E, F) be defined in Proposition 11. Then R_ℓ(f, E, F) = 0for every hyperplane F if and only if T₂(f, E, u) = 0 for every u ≠ 0.

Proof

Clearly, if T₂(f, E, u) = 0 for every u ≠ 0 , then R_ℓ(f, E, F) = 0 for any hyperplane F. Conversely, suppose that R_ℓ(f, E, F) = 0 for every hyperplane F. According to Remark 12, we have 0 ≤ R₁(f, E, F) ≤ R_ℓ(f, E, F) = 0. We then conclude thanks to Proposition 13 that T₂(f, E, u) = 0 for every u ≠ 0. □

4 Boolean functions with constant weight inputs

In this subsection, we shall consider the subsets $E=\{x\in \mathbb {F}_{2}^{n}\mid \text {wt}(x)=k\}$ for 0 ≤ k ≤ n. In the sequel, when x and y are in $\mathbb {F}_{2}^{n}$, we shall denote by z = xy the element of $\mathbb {F}_{2}^{n}$ such that z_i = x_iy_i for every 1 ≤ i ≤ n. Set E + E = {x + y, (x, y) ∈ E²}.

Let us investigate the particular cases where k ∈{0, 1, n − 1, n}. If k = 0, $\widehat {\chi _{f,E}}(a) = (-1)^{f(0)}$ while, if k = n, $\widehat {\chi _{f,E}}(a) = (-1)^{f(1)+\text {wt}(a)}$. In both cases, it implies that NL_E(f) = 0. On the other hand, denote e_i the element of $\mathbb {F}_{2}^{n}$ whose all coordinates are equal to 0 except the i th coordinate. Then, if k = 1, $\widehat {\chi _{f,E}}(a) = {\sum }_{i = 1}^{n}(-1)^{a_{i} + f(e_{i})}$ where a_i stands for the i th-coordinate of a. Now, if a_i = f(e_i) for every 1 ≤ i ≤ n, then $\widehat {\chi _{f,E}}(a) = n$ and thus $NL_{E}(f) = \frac {n}{2} - \frac {1}{2}\max _{a\in \mathbb {F}_{2}^{n}}\vert \widehat {\chi _{f,E}}(a)\vert \leq 0$. If k = n − 1, given $x\in \mathbb {F}_{2}^{n}$, we denote $\bar x$ the element of $\mathbb {F}_{2}^{n}$ such that $\bar x_{i}= 1+x_{i}$. Then, $\widehat {\chi _{f,E}}(a) = {\sum }_{i = 1}^{n}(-1)^{a_{i} + \text {wt}(a) + f(\bar e_{i})}$. Hence, if $a_{i}=f(\bar {e_{i}})+\text {wt}(a)\mod 2$ for every 1 ≤ i ≤ n then, we can conclude as precedingly that NL_E(f) = 0. In the sequel, we shall therefore suppose that 2 ≤ k ≤ n − 2.

Let us now prove the following.

Lemma 15

$E+E=\{x+y,\,(x,y)\in E^{2}\}=\{a\in \mathbb {F}_{2}^{n}\mid \text {wt}(a)\leq \min (2k,n),\, \text {wt}(a)= 0\mod 2\}$. Furthermore, for every $a\in \mathbb {F}_{2}^{n}$, x and x + a are both in E if and only if wt(x) = k and $\text {wt}(ax)=\frac {\text {wt}(a)}{2}$.

Proof

Recall that wt(x + y) = wt(x) + wt(y) − 2wt(xy). Now the latter equation in x has a solution in E for every a of even hamming weight at most 2k. □

According to the above proposition, if u is of even Hamming weight at most 2k,

$$ T_{2}(f,E,u) = \underset{x+y=u}{\sum\limits_{x,y\in E}} (-1)^{f(x)+f(y)} = \underset{\text{wt}(ux)=\frac{\text{wt}(u)}{2}}{\sum\limits_{x\in E}} (-1)^{D_{u}f(x)}, $$

(13)

while T₂(f, E, u) = 0 if wt(u) is odd or greater than 2k. Note, that if u = 0 then T₂(f, E,0) = |E|.

We then establish the following new upper bound on NL_E.

Theorem 16

Let 2 ≤ k ≤ n − 2. Set $E=\{x\in \mathbb {F}_{2}^{n}\mid \text {wt}(x)=k\}$. Let f be a Boolean function over $\mathbb {F}_{2}^{n}$. Then,

$$ NL_{E}(f) \leq \frac{{\left( \begin{array}{c} n \\ k \end{array}\right)}}{2} - \frac{1}{2}\sqrt{{\left( \begin{array}{c} n \\ k \end{array}\right)} + \lambda + \max\left( \theta,\frac{1}{{\left( \begin{array}{c} n \\ k \end{array}\right)}}\gamma-\lambda\right)}, $$

(14)

where

$$ \lambda = \underset{\text{wt}(u)\equiv 0~(\bmod 2)}{\max\limits_{u\not= 0}}\left\vert \underset{\text{wt}(u x)=\frac{\text{wt}(u)}{2}}{\sum\limits_{x\in E}} (-1)^{D_{u} f(x)}\right\vert, $$

(15)

$$ \gamma = \underset{\text{wt}(u)\equiv 0~(\bmod 2)}{\sum\limits_{u\not= 0}}\left( \underset{\text{wt}(u x)=\frac{\text{wt}(u)}{2}}{\sum\limits_{x\in E}} (-1)^{D_{u} f(x)}\right)^{2} $$

(16)

and

$$ \theta = \frac{1}{{\left( \begin{array}{c} n \\ k \end{array}\right)}+\lambda}\left( \gamma-\lambda^{2}\right)\geq 0. $$

(17)

Proof

Let γ ≠ 0 be such that |T₂(f, E, γ)| = λ. According to Equation (8), when F = {0, γ}^⊥:

$$\begin{array}{@{}rcl@{}} \frac{S_{4}(f,E,F)}{S_{2}(f,E,F)} &=& |E| + T_{2}(f,E,\gamma) + \frac{{\sum}_{\underset{u, v\not\in\{0,\gamma\}}{u+v\in\{0,\gamma\}}} T_{2}(f,E,u)T_{2}(f,E,v)}{|E| + T_{2}(f,E,\gamma)} \end{array} $$

We have to distinguish two cases depending on the sign of T₂(f, E, γ):

• If T₂(f, E, γ) is nonnegative, then

  $$\begin{array}{@{}rcl@{}} \frac{S_{4}(f,E,F)}{S_{2}(f,E,F)} = |E| + \lambda + \frac{{\sum}_{\underset{u, v\not\in\{0,\gamma\}}{u+v\in\{0,\gamma\}}} T_{2}(f,E,u)T_{2}(f,E,v)}{|E| + \lambda} \end{array} $$

  Now

  $$\begin{array}{@{}rcl@{}} \underset{u, v\not\in\{0,\gamma\}}{\sum\limits_{u+v\in\{0,\gamma\}}} T_{2}(f,E,u)T_{2}(f,E,v) \,=\, \sum\limits_{u\not\in\{0,\gamma\}} \left( T_{2}(f,E,u)\right)^{2} \,+\, \sum\limits_{u\not\in\{0,\gamma\}} T_{2}(f,E,u)T_{2}(f,E,u\,+\,\gamma) \end{array} $$

  and therefore

  $$\begin{array}{@{}rcl@{}} \frac{S_{4}(f,E,F)}{S_{2}(f,E,F)} = |E| + \lambda + \frac{ {\sum}_{u\not\in\{0,\gamma\}} \left( T_{2}(f,E,u)\right)^{2} + {\sum}_{u\not\in\{0,\gamma\}} T_{2}(f,E,u)T_{2}(f,E,u+\gamma)}{|E| + \lambda} \end{array} $$

• If T₂(f, E, γ) is negative, that is, T₂(f, E, γ) = −λ. Set f_v(x) = f(x) + v ⋅ x with v ≠ 0. Observe that $T_{2}(f_{v},E,u)=\underset {x+y=u}{\sum \limits _{x,y\in E}} (-1)^{f_{v}(x)+f_{v}(y)}=(-1)^{v\cdot u}T_{2}(f,E,u)$ for every $u\in \mathbb {F}_{2}^{n}$. If we choose v such that v ⋅ γ = 1 (such v exists since γ ≠ 0), then we have T₂(f_v, E, γ) = −T₂(f, E, γ) = λ. Furthermore,

  $$\begin{array}{@{}rcl@{}} \frac{S_{4}(f_{v},E,F)}{S_{2}(f_{v},E,F)} \,=\, |E| + \lambda + \frac{ {\sum}_{u\not\in\{0,\gamma\}} \left( T_{2}(f,E,u)\right)^{2} - {\sum}_{u\not\in\{0,\gamma\}} T_{2}(f,E,u)T_{2}(f,E,u\!+\gamma)}{|E| + \lambda} \end{array} $$

Now

$$\begin{array}{@{}rcl@{}} \left( \vert E\vert - 2NL_{E}(f) \right)^{2} \geq \frac{S_{4}(f,E,F)}{S_{2}(f,E,F)} \end{array} $$

and, according to Lemma 2, NL_E(f_v) = NL_E(f). Thus

$$\begin{array}{@{}rcl@{}} \left( \vert E\vert - 2NL_{E}(f) \right)^{2} \geq \frac{S_{4}(f_{v},E,F)}{S_{2}(f_{v},E,F)} \end{array} $$

We therefore conclude from the two above decompositions of $\frac {S_{4}(f,E,F)}{S_{2}(f,E,F)}$ and $\frac {S_{4}(f_{v},E,F)}{S_{2}(f_{v},E,F)}$ that:

$$\begin{array}{@{}rcl@{}} \left( \vert E\vert - 2NL_{E}(f) \right)^{2} \geq |E| + \lambda + \frac{ {\sum}_{u\not\in\{0,\gamma\}} \left( T_{2}(f,E,u)\right)^{2}}{|E| + \lambda} \end{array} $$

proving

$$ NL_{E}(f) \leq \frac{\vert E\vert}{2} - \frac{1}{2}\sqrt{|E| + \lambda + \frac{ {\sum}_{u\not\in\{0,\gamma\}} \left( T_{2}(f,E,u)\right)^{2}}{|E| + \lambda}}. $$

(18)

Next, according to (10), when F = {0, γ}^⊥ with γ of odd weight,

$$\begin{array}{@{}rcl@{}} \frac{S_{4}(f,E,F)}{S_{2}(f,E,F)} &=& |E| + \frac{\underset{u, v\not\in\{0,\gamma\}}{\sum\limits_{u+v\in\{0,\gamma\}}} T_{2}(f,E,u)T_{2}(f,E,v)}{|E|}, \end{array} $$

since T₂(f, E, γ) = 0. Now, if γ is of odd weight, then, for every u∉{0, γ}, the weights of u and u + γ are of different parity since wt(u + γ) = wt(u) + wt(γ) − 2wt(uγ). Thus T₂(f, E, u)T₂(f, E, u + γ) = 0 for every u∉{0, γ} according to Lemma 15. Then, we simply get in that case (since T₂(f, E, γ) = 0)

$$\begin{array}{@{}rcl@{}} \frac{S_{4}(f,E,F)}{S_{2}(f,E,F)} &=& |E| + \frac{1}{|E|}{\sum}_{u\not= 0}\left( T_{2}(f,E,u)\right)^{2}. \end{array} $$

yielding that

$$ NL_{E}(f) \leq \frac{\vert E\vert}{2} - \frac{1}{2}\sqrt{ |E| + \frac{1}{|E|}\sum\limits_{u\not= 0}\left( T_{2}(f,E,u)\right)^{2}} $$

(19)

Proposition 16 follows then from (18) and (19). □

Remark 17

Observe that

$$\begin{array}{@{}rcl@{}} \theta - \left( \frac{1}{{\left( \begin{array}{c} n \\ k \end{array}\right)}}\gamma-\lambda\right) &=& \frac{1}{{\left( \begin{array}{c} n \\ k \end{array}\right)}+\lambda}\left( \gamma-\lambda^{2}\right) - \left( \frac{1}{{\left( \begin{array}{c} n \\ k \end{array}\right)}}\gamma-\lambda\right)\\ &=& \frac{\lambda}{{\left( \begin{array}{c} n \\ k \end{array}\right)}\left( {\left( \begin{array}{c} n \\ k \end{array}\right)}+\lambda\right)}\left( {\left( \begin{array}{c} n \\ k \end{array}\right)}^{2} - \gamma\right). \end{array} $$

Thus

$$\begin{array}{@{}rcl@{}} \max\left( \theta,\frac{1}{{\left( \begin{array}{c} n \\ k \end{array}\right)}}\gamma-\lambda\right) = \left\{\begin{array}{ll} \theta & \text{if }\gamma\leq {\left( \begin{array}{c} n \\ k \end{array}\right)}^{2}\\ \frac{1}{{\left( \begin{array}{c} n \\ k \end{array}\right)}}\gamma-\lambda & \text{if }\gamma > {\left( \begin{array}{c} n \\ k \end{array}\right)}^{2} \end{array}\right. \end{array} $$

We indicate that, if $\gamma > {\left (\begin {array}{c} n \\ k \end {array}\right )}^{2}$ then $\frac {1}{{\left (\begin {array}{c} n \\ k \end {array}\right )}}\gamma -\lambda >{\left (\begin {array}{c} n \\ k \end {array}\right )}-\lambda \geq 0$.

Remark 18

Observe that, if there exists u₁≠u₂ such that |T₂(f, E, u₁)| = |T₂(f, E, u₂)| = λ, γ ≥ 2λ² > λ² yielding that 𝜃 > 0. Therefore, $\max \left (\theta ,\frac {1}{{\left (\begin {array}{c} n \\ k \end {array}\right )}}\gamma -\lambda \right )= 0$ if and only if there exists a unique u ≠ 0 such that |T₂(f, E, u)| = λ and 𝜃 = 0, that is, |T₂(f, E, v)| = 0 for every v∉{0, u} (observe that γ = T₂(f, E, u)² = λ² and $\frac {1}{{\left (\begin {array}{c} n \\ k \end {array}\right )}}\gamma -\lambda =\frac {1}{{\left (\begin {array}{c} n \\ k \end {array}\right )}}\lambda (\lambda -{\left (\begin {array}{c} n \\ k \end {array}\right )})\leq 0$). In other words, if we are not in this situation, $\max \left (\theta ,\frac {1}{{\left (\begin {array}{c} n \\ k \end {array}\right )}}\gamma -\lambda \right )$ is positive.

5 Concluding remarks

In the line of the very recent work of Carlet, Méaux and Rotella, we provided a further study of Boolean functions with restricted input. Inspired by the work of Carlet and the first author on the covering radii of binary Reed-Muller codes, we firstly obtained upper bounds on the nonlinearity for Boolean functions with general restricted input. Next, we derived an upper bound in the particular case when the restricted input is the set of vectors of fixed Hamming weight. Our results improved the known upper bound given by Carlet et al. It would be interesting to construct Boolean functions approaching those developed bounds. But such construction would be a very hard work. The reader is kindly invited to join this adventure.