Boolean Functions: Difference between revisions

From Boolean
Jump to navigation Jump to search
mNo edit summary
mNo edit summary
Line 99: Line 99:
* If ๐‘“,๐‘” are affine equivalent, then <math>W_g(u)=(-1)^{u\cdot L^{-1}(a)}W_f(L^{-1}(u))</math>.
* If ๐‘“,๐‘” are affine equivalent, then <math>W_g(u)=(-1)^{u\cdot L^{-1}(a)}W_f(L^{-1}(u))</math>.


=The Nonlinearity=
=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,
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>
<center><math> \mathcal{NL}(f)=\min_{g\in\mathcal{A}}d_H(f,g)</math></center>
Line 105: Line 112:
* 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>.
* 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>.
* 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 <em>bent</em> (๐‘› is an even integer).
* A function achieving the covering radius bound with equality is called <em>bent</em> (๐‘› 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 ๐‘Š<sub>๐‘“</sub>(๐‘ข)=ยฑ2<sup>๐‘›/2</sup>, for every ๐‘ขโˆˆ๐”ฝ<sub>2</sub><sup>๐‘›</sup>.
==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>

Revision as of 15:51, 11 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 [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

[math]\displaystyle{ f(x)=\bigoplus_{I\subseteq\{1,\ldots,n\}}a_i\Big(\prod_{i\in I}x_i\Big)\in\mathbb{F}_2[x_1,\ldots,x_n]/(x_1^2\oplus x_1,\ldots,x_n^2\oplus x_n). }[/math]

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

[math]\displaystyle{ f(x)=\sum_{j\in\Gamma_n}\mbox{Tr}_{\mathbb{F}_{2^{o(j)}}/\mathbb{F}_2}(A_jx^j), \quad x\in\mathbb{F}_{2^n}, }[/math]

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.

When we consider the trace representation of of a function, then the algebraic degree is given by [math]\displaystyle{ \max_{j\in\Gamma_n | A_j\ne0}w_2(j) }[/math], 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)

[math]\displaystyle{ W_f(u)=\sum_{x\in\mathbb{F}_2^n}(-1)^{f(x)+x\cdot u}, }[/math]

The set [math]\displaystyle{ \{ u\in\mathbb{F}_2^n : W_f(u)\ne0 \}=\{ u\in\mathbb{F}_2^n : W_f(u)=1 \} }[/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 ๐‘ฅโˆˆ๐ธ}.

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 [math]\displaystyle{ 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 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,

[math]\displaystyle{ \mathcal{NL}(f)=\min_{g\in\mathcal{A}}d_H(f,g) }[/math]
  • For every ๐‘“ we have [math]\displaystyle{ \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 covering radius bound [math]\displaystyle{ \mathcal{NL}(f)\le2^{n-1}-2^{n/2-1} }[/math].
  • 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๐‘›.

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.