Difference between revisions of "Boolean Functions"

From Boolean Functions
Jump to: navigation, search
m (β†’β€ŽThe Nonlinearity)
 
(11 intermediate revisions by the same user not shown)
Line 8: Line 8:
 
The Hamming weight of π‘₯ is the size of its support (<math>w_H(x)=|supp_x|</math>).
 
The Hamming weight of π‘₯ is the size of its support (<math>w_H(x)=|supp_x|</math>).
 
Similarly the Hamming weight of a Boolean function 𝑓 is the size of its support, i.e. the set <math>\{x\in\mathbb{F}_2^n : f(x)\ne0 \}</math>.
 
Similarly the Hamming weight of a Boolean function 𝑓 is the size of its support, i.e. the set <math>\{x\in\mathbb{F}_2^n : f(x)\ne0 \}</math>.
βˆ’
The Hamming distance of two functions 𝑓,𝑔 is the size of the set <math>\{x\in\mathbb{F}_2^n : f(x)\neq g(x) \}\ (w_H(f\oplus g))</math>.
+
The Hamming distance of two functions 𝑓,𝑔 (𝖽<sub>𝐻</sub>(𝑓,𝑔)) is the size of the set <math>\{x\in\mathbb{F}_2^n : f(x)\neq g(x) \}\ (w_H(f\oplus g))</math>.
  
 
=Representation of a Boolean function=
 
=Representation of a Boolean function=
Line 52: Line 52:
  
 
The degree of the ANF is called the <em> algebraic degree</em> of the function, 𝑑°𝑓=max { |𝐼| : π‘Ž<sub>𝐼</sub>&ne;0 }.
 
The degree of the ANF is called the <em> algebraic degree</em> of the function, 𝑑°𝑓=max { |𝐼| : π‘Ž<sub>𝐼</sub>&ne;0 }.
 +
 +
Based on the algebraic degree we called 𝑓
 +
* <em>affine</em> if 𝑑°𝑓=1, <em>linear</em> if 𝑑°𝑓=1 and 𝑓(𝟎)=0;
 +
* <em>quadratic</em> if 𝑑°𝑓=2.
 +
Affine functions are of the form 𝑓(π‘₯)= 𝑒⋅π‘₯+𝑒, for π‘’βˆˆπ”½<sub>2</sub><sup>𝑛</sup> and π‘’βˆˆπ”½<sub>2</sub>
  
 
==Trace representation==
 
==Trace representation==
Line 63: Line 68:
  
 
𝑓 can also be simply presented in the form <math> \mbox{Tr}_{\mathbb{F}_{2^n}/\mathbb{F}_2}(P(x))</math>  where π˜— is a polynomial over the finite field F<sub>2<sup>𝑛</sup></sub> but such representation is not unique, unless 𝘰(𝘫)=𝑛 for every 𝘫 such that 𝘈<sub>𝘫</sub>&ne;0.
 
𝑓 can also be simply presented in the form <math> \mbox{Tr}_{\mathbb{F}_{2^n}/\mathbb{F}_2}(P(x))</math>  where π˜— is a polynomial over the finite field F<sub>2<sup>𝑛</sup></sub> but such representation is not unique, unless 𝘰(𝘫)=𝑛 for every 𝘫 such that 𝘈<sub>𝘫</sub>&ne;0.
 +
 +
When we consider the trace representation of of a function, then the algebraic degree is given by <math>\max_{j\in\Gamma_n | A_j\ne0}w_2(j)</math>, where π“Œ<sub>2</sub>(𝑗) is the Hamming weight of the binary expansion of 𝑗.
 +
 +
=On the weight of a Boolean function=
 +
For 𝑓 a 𝑛-variable Booleand function the following relations about its weight are satisfied.
 +
* If 𝑑°𝑓=1 then π“Œ<sub>𝐻</sub>(𝑓)=2<sup>𝑛-1</sup>.
 +
* If 𝑑°𝑓=2 then π“Œ<sub>𝐻</sub>(𝑓)=2<sup>𝑛-1</sup> or π“Œ<sub>𝐻</sub>(𝑓)=2<sup>𝑛-1</sup>Β±2<sup>𝑛-1-β„Ž</sup>, with 0β‰€β„Žβ‰€π‘›/2.
 +
* If π‘‘Β°π‘“β‰€π‘Ÿ and 𝑓 nonzero then π“Œ<sub>𝐻</sub>(𝑓)β‰₯2<sup>𝑛-π‘Ÿ</sup>.
 +
* π“Œ<sub>𝐻</sub>(𝑓) is odd if and only if 𝑑°𝑓=𝑛.
  
 
=The Walsh transform=
 
=The Walsh transform=
Line 68: Line 82:
 
With an innner product in 𝔽<sub>2</sub><sup>𝑛</sup> π‘₯·𝑦, the value of π‘Š<sub>𝑓</sub> at π‘’βˆˆπ”½<sub>2</sub><sup>𝑛</sup> is the following sum (over the integers)
 
With an innner product in 𝔽<sub>2</sub><sup>𝑛</sup> π‘₯·𝑦, the value of π‘Š<sub>𝑓</sub> at π‘’βˆˆπ”½<sub>2</sub><sup>𝑛</sup> is the following sum (over the integers)
 
<center><math>W_f(u)=\sum_{x\in\mathbb{F}_2^n}(-1)^{f(x)+x\cdot u},</math></center>
 
<center><math>W_f(u)=\sum_{x\in\mathbb{F}_2^n}(-1)^{f(x)+x\cdot u},</math></center>
βˆ’
The set <math>\{ u\in\mathbb{F}_2^n : W_f(u)\ne0 \}</math> is the <i>Walsh support</i> of 𝑓.
+
The set <math>\{ u\in\mathbb{F}_2^n : W_f(u)\ne0 \}=\{ u\in\mathbb{F}_2^n : W_f(u)=1 \}</math> is the <i>Walsh support</i> of 𝑓.
  
 
==Properties of the Walsh transform==
 
==Properties of the Walsh transform==
Line 76: Line 90:
 
* Poisson summation formula: for any vector subspace 𝐸 of 𝔽<sub>2</sub><sup>𝑛</sup> and for any elements π‘Ž,𝑏 in 𝔽<sub>2</sub><sup>𝑛</sup> <center><math> \sum_{u\in a+E^\perp}(-1)^{b\cdot u}W_f(u) = |E^\perp|(-1)^{a\cdot b}\sum_{x\in b+E}(-1)^{f(x)+a\cdot x},</math></center>  for 𝐸<sup>βŸ‚</sup> the orthogonal subspace of 𝐸,{π‘’βˆˆπ”½<sub>2</sub><sup>𝑛</sup> : 𝑒·π‘₯=0, for all π‘₯∈𝐸}.
 
* Poisson summation formula: for any vector subspace 𝐸 of 𝔽<sub>2</sub><sup>𝑛</sup> and for any elements π‘Ž,𝑏 in 𝔽<sub>2</sub><sup>𝑛</sup> <center><math> \sum_{u\in a+E^\perp}(-1)^{b\cdot u}W_f(u) = |E^\perp|(-1)^{a\cdot b}\sum_{x\in b+E}(-1)^{f(x)+a\cdot x},</math></center>  for 𝐸<sup>βŸ‚</sup> the orthogonal subspace of 𝐸,{π‘’βˆˆπ”½<sub>2</sub><sup>𝑛</sup> : 𝑒·π‘₯=0, for all π‘₯∈𝐸}.
  
βˆ’
=Equivalence of Boolean functions=
+
=Equivalences of Boolean functions=
βˆ’
Two 𝑛-variable Boolean functions 𝑓,𝑔 are called <i>extended-affine equivalent</i> (shortly EA-equivalent) if there exists a linear automorphism 𝐿, an affine Boolean function 𝓁 and a vecor π‘Ž such that 𝑔(π‘₯) = 𝑓(𝐿(π‘₯)+π‘Ž)+𝓁(π‘₯).
+
Two 𝑛-variable Boolean functions 𝑓,𝑔 are called <i>affine equivalent</i> if there exists a linear automorphism 𝐿 and a vecor π‘Ž such that <center>𝑔(π‘₯) = 𝑓(𝐿(π‘₯)+π‘Ž).</center>
βˆ’
A parameter that is preserved by EA-equivalence is called <i>EA-invariant</i>.
+
 
 +
Two 𝑛-variable Boolean functions 𝑓,𝑔 are called <i>extended-affine equivalent</i> (shortly EA-equivalent) if there exists a linear automorphism 𝐿, an affine Boolean function 𝓁 and a vecor π‘Ž such that <center>𝑔(π‘₯) = 𝑓(𝐿(π‘₯)+π‘Ž)+𝓁(π‘₯).</center>
 +
A parameter that is preserved by an equivalence relation is called <i>invariant</i>.
 +
 
 +
* The degree is invariant under affine equivalence and, for not affine functions, also under EA-equivalence.
 +
* If 𝑓,𝑔 are affine equivalent, then <math>W_g(u)=(-1)^{u\cdot L^{-1}(a)}W_f(L^{-1}(u))</math>.
 +
 
 +
=Properties important for cryptographic applications=
 +
 
 +
==Balanced functions==
 +
An 𝑛-variable Boolean function 𝑓 is called <em>balanced</em> if π“Œ<sub>𝐻</sub>(𝑓)=2<sup>𝑛-1</sup>, so its output is uniformly distributed.
 +
Such functions cannot have maximal degree.
 +
Most cryptographic applications use balanced Boolean functions.
 +
 
 +
==The Nonlinearity==
 +
The <em>nonlinearity</em> of a function 𝑓 is defined as its minimal distance to affine functions, i.e. called π’œ the set of all affine 𝑛-variable functions,
 +
<center><math> \mathcal{NL}(f)=\min_{g\in\mathcal{A}}d_H(f,g)</math></center>
 +
 
 +
* For every 𝑓 we have <math>\mathcal{NL}(f)=2^{n-1}-\frac{1}{2}\max_{u\in\mathbb{F}_2^n}|W_f(u)|</math>.
 +
* From Parseval relation we obtain the <em>covering radius bound</em> <math>\mathcal{NL}(f)\le2^{n-1}-2^{n/2-1}</math>.
 +
* A function achieving the covering radius bound with equality is called [[Bent Boolean Functions| bent]] (𝑛 is an even integer and the function is not balanced).
 +
* 𝑓 is bent if and only if π‘Š<sub>𝑓</sub>(𝑒)=Β±2<sup>𝑛/2</sup>, for every π‘’βˆˆπ”½<sub>2</sub><sup>𝑛</sup>.
 +
* 𝑓 is bent if and only if for any nonzero element π‘Ž the Boolean function 𝐷<sub>π‘Ž</sub>𝑓(π‘₯)=𝑓(π‘₯+π‘Ž)+𝑓(π‘₯) is balanced.
 +
 
 +
==Correlation-immunity order==
 +
A Boolean function 𝑓 is <em>π‘š-th order correlation-immune</em> if the probability distribution of the output is unaltered when any π‘š input variables are fixed.
 +
Balanced π‘š-th order correlation-immune functions are called <em>π‘š-resilient</em>.
 +
 
 +
Given 𝑓 a 𝑛-variable function with correlation-immunity of order π‘š then <center>π‘š+𝑑°𝑓≀𝑛.</center>
 +
If 𝑓 is also balanced, then <center>π‘š+𝑑°𝑓≀𝑛-1.</center>

Latest revision as of 15:39, 25 October 2019

Introduction

Let 𝔽2𝑛 be the vector space of dimension 𝑛 over the finite field with two elements. The vector space can also be endowed with the structure of the field, the finite field with 2𝑛 elements, 𝔽2𝑛. A function is called a Boolean function in dimenstion 𝑛 (or 𝑛-variable Boolean function).

Given , the support of x is the set . The Hamming weight of π‘₯ is the size of its support (). Similarly the Hamming weight of a Boolean function 𝑓 is the size of its support, i.e. the set . The Hamming distance of two functions 𝑓,𝑔 (𝖽𝐻(𝑓,𝑔)) is the size of the set .

Representation of a Boolean function

There exist different ways to represent a Boolean function. A simple, but often not efficient, one is by its truth-table. For example consider the following truth-table for a 3-variable Boolean function 𝑓.

π‘₯ 𝑓(π‘₯)
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1

Algebraic normal form

An 𝑛-variable Boolean function can be represented by a multivariate polynomial over 𝔽2 of the form

Such representation is unique and it is the algebraic normal form of 𝑓 (shortly ANF).

The degree of the ANF is called the algebraic degree of the function, 𝑑°𝑓=max { |𝐼| : π‘ŽπΌ≠0 }.

Based on the algebraic degree we called 𝑓

  • affine if 𝑑°𝑓=1, linear if 𝑑°𝑓=1 and 𝑓(𝟎)=0;
  • quadratic if 𝑑°𝑓=2.

Affine functions are of the form 𝑓(π‘₯)= 𝑒⋅π‘₯+𝑒, for π‘’βˆˆπ”½2𝑛 and π‘’βˆˆπ”½2

Trace representation

We identify the vector space with the finite field and we consider 𝑓 an 𝑛-variable Boolean function of even weight (hence of algebraic degree at most 𝑛-1). The map admits a uinque representation as a univariate polynomial of the form

with Γ𝑛 set of integers obtained by choosing one element in each cyclotomic coset of 2 ( mod 2𝑛-1), 𝘰(𝘫) size of the cyclotomic coset containing 𝘫, 𝘈𝘫 ∈ 𝔽2𝘰(𝘫), Tr𝔽2𝘰(𝘫)/𝔽2 trace function from 𝔽2𝘰(𝘫) to 𝔽2.

Such representation is also called the univariate representation .

𝑓 can also be simply presented in the form where π˜— is a polynomial over the finite field F2𝑛 but such representation is not unique, unless 𝘰(𝘫)=𝑛 for every 𝘫 such that 𝘈𝘫≠0.

When we consider the trace representation of of a function, then the algebraic degree is given by , where π“Œ2(𝑗) is the Hamming weight of the binary expansion of 𝑗.

On the weight of a Boolean function

For 𝑓 a 𝑛-variable Booleand function the following relations about its weight are satisfied.

  • If 𝑑°𝑓=1 then π“Œπ»(𝑓)=2𝑛-1.
  • If 𝑑°𝑓=2 then π“Œπ»(𝑓)=2𝑛-1 or π“Œπ»(𝑓)=2𝑛-1Β±2𝑛-1-β„Ž, with 0β‰€β„Žβ‰€π‘›/2.
  • If π‘‘Β°π‘“β‰€π‘Ÿ and 𝑓 nonzero then π“Œπ»(𝑓)β‰₯2𝑛-π‘Ÿ.
  • π“Œπ»(𝑓) is odd if and only if 𝑑°𝑓=𝑛.

The Walsh transform

The Walsh transform π‘Šπ‘“ is the descrete Fourier transform of the sign function of 𝑓, i.e. (-1)𝑓(π‘₯). With an innner product in 𝔽2𝑛 π‘₯·𝑦, the value of π‘Šπ‘“ at π‘’βˆˆπ”½2𝑛 is the following sum (over the integers)

The set is the Walsh support of 𝑓.

Properties of the Walsh transform

For every 𝑛-variable Boolean function 𝑓 we have the following relations.

  • Inverse Walsh transform: for any element π‘₯ of 𝔽2𝑛 we have
  • Parseval's relation:
  • Poisson summation formula: for any vector subspace 𝐸 of 𝔽2𝑛 and for any elements π‘Ž,𝑏 in 𝔽2𝑛
    for πΈβŸ‚ the orthogonal subspace of 𝐸,{π‘’βˆˆπ”½2𝑛 : 𝑒·π‘₯=0, for all π‘₯∈𝐸}.

Equivalences of Boolean functions

Two 𝑛-variable Boolean functions 𝑓,𝑔 are called affine equivalent if there exists a linear automorphism 𝐿 and a vecor π‘Ž such that

𝑔(π‘₯) = 𝑓(𝐿(π‘₯)+π‘Ž).

Two 𝑛-variable Boolean functions 𝑓,𝑔 are called extended-affine equivalent (shortly EA-equivalent) if there exists a linear automorphism 𝐿, an affine Boolean function 𝓁 and a vecor π‘Ž such that

𝑔(π‘₯) = 𝑓(𝐿(π‘₯)+π‘Ž)+𝓁(π‘₯).

A parameter that is preserved by an equivalence relation is called invariant.

  • The degree is invariant under affine equivalence and, for not affine functions, also under EA-equivalence.
  • If 𝑓,𝑔 are affine equivalent, then .

Properties important for cryptographic applications

Balanced functions

An 𝑛-variable Boolean function 𝑓 is called balanced if π“Œπ»(𝑓)=2𝑛-1, so its output is uniformly distributed. Such functions cannot have maximal degree. Most cryptographic applications use balanced Boolean functions.

The Nonlinearity

The nonlinearity of a function 𝑓 is defined as its minimal distance to affine functions, i.e. called π’œ the set of all affine 𝑛-variable functions,

  • For every 𝑓 we have .
  • From Parseval relation we obtain the covering radius bound .
  • A function achieving the covering radius bound with equality is called bent (𝑛 is an even integer and the function is not balanced).
  • 𝑓 is bent if and only if π‘Šπ‘“(𝑒)=Β±2𝑛/2, for every π‘’βˆˆπ”½2𝑛.
  • 𝑓 is bent if and only if for any nonzero element π‘Ž the Boolean function π·π‘Žπ‘“(π‘₯)=𝑓(π‘₯+π‘Ž)+𝑓(π‘₯) is balanced.

Correlation-immunity order

A Boolean function 𝑓 is π‘š-th order correlation-immune if the probability distribution of the output is unaltered when any π‘š input variables are fixed. Balanced π‘š-th order correlation-immune functions are called π‘š-resilient.

Given 𝑓 a 𝑛-variable function with correlation-immunity of order π‘š then

π‘š+𝑑°𝑓≀𝑛.

If 𝑓 is also balanced, then

π‘š+𝑑°𝑓≀𝑛-1.