Boolean Functions: Difference between revisions
No edit summary |
|||
Line 77: | Line 77: | ||
=Equivalence of Boolean functions= | =Equivalence 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>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 EA-equivalence is called <i>EA-invariant</i>. | A parameter that is preserved by EA-equivalence is called <i>EA-invariant</i>. |
Revision as of 09:29, 27 September 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 [math]\displaystyle{ f : \mathbb{F}_2^n\rightarrow\mathbb{F} }[/math] is called a Boolean function in dimenstion 𝑛 (or 𝑛-variable Boolean function).
Given [math]\displaystyle{ x=(x_1,\ldots,x_n)\in\mathbb{F}_2^n }[/math], the support of x is the set [math]\displaystyle{ supp_x=\{i\in\{1,\ldots,n\} : x_i=1 \} }[/math]. The Hamming weight of 𝑥 is the size of its support ([math]\displaystyle{ 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]\displaystyle{ \{x\in\mathbb{F}_2^n : f(x)\ne0 \} }[/math]. The Hamming distance of two functions 𝑓,𝑔 is the size of the set [math]\displaystyle{ \{x\in\mathbb{F}_2^n : f(x)\neq g(x) \}\ (w_H(f\oplus g)) }[/math].
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 }.
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 [math]\displaystyle{ \mbox{Tr}_{\mathbb{F}_{2^n}/\mathbb{F}_2}(P(x)) }[/math] where 𝘗 is a polynomial over the finite field F2𝑛 but such representation is not unique, unless 𝘰(𝘫)=𝑛 for every 𝘫 such that 𝘈𝘫≠0.
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 [math]\displaystyle{ \{ u\in\mathbb{F}_2^n : W_f(u)\ne0 \} }[/math] 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
[math]\displaystyle{ \sum_{u\in\mathbb{F}_2^n}W_f(u)(-1)^{u\cdot x}= 2^n(-1)^{f(x)}; }[/math] - Parseval's relation:
[math]\displaystyle{ \sum_{u\in\mathbb{F}_2^n}W_f^2(u)=2^{2n}; }[/math] - Poisson summation formula: for any vector subspace 𝐸 of 𝔽2𝑛 and for any elements 𝑎,𝑏 in 𝔽2𝑛
[math]\displaystyle{ \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] for 𝐸⟂ the orthogonal subspace of 𝐸,{𝑢∈𝔽2𝑛 : 𝑢·𝑥=0, for all 𝑥∈𝐸}.
Equivalence of Boolean functions
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 EA-equivalence is called EA-invariant.