Niho bent functions: Difference between revisions

From Boolean
Jump to navigation Jump to search
(Created page with " == Background and Definitions == '''Definition.''' A power boolean function π‘₯<sup>𝑑</sup> defined on 𝔽<sub>2<sup>𝑛</sup></sub> is called a ''Niho power functio...")
Β 
No edit summary
Β 
(One intermediate revision by the same user not shown)
Line 5: Line 5:
'''Definition.''' A power boolean function π‘₯<sup>𝑑</sup>Β  defined on 𝔽<sub>2<sup>𝑛</sup></sub> is called a ''Niho power function'', ifΒ  its
'''Definition.''' A power boolean function π‘₯<sup>𝑑</sup>Β  defined on 𝔽<sub>2<sup>𝑛</sup></sub> is called a ''Niho power function'', ifΒ  its
restriction to 𝔽<sub>2<sup>m</sup></sub> is linear, where n=2m.
restriction to 𝔽<sub>2<sup>m</sup></sub> is linear, where n=2m.
''Niho bent functions'' are [[bent functions]] with Niho exponents.


'''Niho bent functions''' in bivariant form:
'''Niho bent functions''' in bivariant form:
Line 17: Line 19:
where μ∈ 𝔽<sub>2<sup>m</sup></sub>, 𝐺 :𝔽<sub>2<sup>m</sup></sub> β†’ 𝔽<sub>2<sup>m</sup></sub> satisfying the following conditions:
where μ∈ 𝔽<sub>2<sup>m</sup></sub>, 𝐺 :𝔽<sub>2<sup>m</sup></sub> β†’ 𝔽<sub>2<sup>m</sup></sub> satisfying the following conditions:


𝐹 : 𝑧 β†’ G(𝑧)+μ𝑧 is a permutation over 𝔽<sub>2<sup>m</sup></sub>,
𝐹 : 𝑧 β†’ G(𝑧)+μ𝑧 is a permutation over 𝔽<sub>2<sup>m</sup></sub>, Β  Β  (1)
Β 
z →𝐹(𝑧)+β𝑧 is 2-to-1 on 𝔽<sub>2<sup>m</sup></sub>Β  for any nonzeroΒ  Ξ²βˆˆπ”½<sub>2<sup>m</sup></sub> .Β  Β  (2)
Β 


z →𝐹(𝑧)+β𝑧 is 2-to-1 on 𝔽<sub>2<sup>m</sup></sub> for any nonzeroΒ  Ξ²βˆˆπ”½<sub>2<sup>m</sup></sub> .
Here condition (2) implies condition (1) and it is necessary and suffcient for g
being bent.
Β 
One can get a univariate representation of Niho bent function from bivariant one making the following substitutions:
x=t+t<sup>2<sup>m</sup></sup> and y=Ξ±t +(Ξ±t)<sup>2<sup>m</sup></sup>,
where Ξ± is a primitive element of 𝔽<sub>2<sup>m</sup></sub> .


== Examples ==
== Examples ==
Line 29: Line 39:
π‘Žβˆˆπ”½<sub>2<sup>m</sup></sub>.
π‘Žβˆˆπ”½<sub>2<sup>m</sup></sub>.


2. Binomials of the formΒ  𝑓(𝑑)= Tr<sub>n</sub>(Ξ±<sub>1</sub>𝑑<sup>𝑑<sub>1</sub></sup>+Ξ±<sub>2</sub>𝑑<sup>𝑑<sub>1</sub></sup>),
2. Binomials of the formΒ  𝑓(𝑑)= Tr<sub>n</sub>(Ξ±<sub>1</sub>𝑑<sup>𝑑<sub>1</sub></sup>+Ξ±<sub>2</sub>𝑑<sup>𝑑<sub>1</sub></sup>),where
where 2<sup>𝑑<sub>1</sub></sup>\equiv 2<sup>m<sub>1</sub>+1</sup> mod(2<sup>n</sup>-1) and Ξ±<sub>1</sub>, Ξ±<sub>2</sub>βˆˆπ”½<sub>2<sup>m</sup></sub> are such that (Ξ±<sub>1</sub>+Ξ±<sub>1</sub><sup>2<sup>m</sup></sup>)<sup>2</sup>=Ξ±<sub>2</sub><sup>2<sup>m</sup>+1</sup>.
Β 
These functions have algebraic degree $m$ and do not belong to the completed Maiorana-McFarland class.
2<sup>𝑑<sub>1</sub></sup>≑ 2<sup>m<sub>1</sub>+1</sup> mod(2<sup>n</sup>-1) and Ξ±<sub>1</sub>, Ξ±<sub>2</sub>βˆˆπ”½<sup>*</sup><sub>2<sup>n</sup></sub> are such that (Ξ±<sub>1</sub>+Ξ±<sub>1</sub><sup>2<sup>m</sup></sup>)<sup>2</sup>=Ξ±<sub>2</sub><sup>2<sup>m</sup>+1</sup>.
These functions have algebraic degree m and do not belong to the completed Maiorana-McFarland class.
Β 
3. Let 1 < r < m with gcd(r,m) = 1,
Β 
𝑓(𝑑)= Tr<sub>n</sub>(a<sup>2</sup>t<sup>2<sup>m</sup>+1</sup>+(a+a<sup>2<sup>m</sup></sup>)<math> \sum_{i=1}^{2^{r-1}-1}t^{d_i}</math>),


3. 𝑓(𝑑)= Tr<sub>n</sub>(a<sup>2</sup>t<sup>2<sup>m</sup>+1</sup>+(a+a<sup>2<sup>m</sup></sup>)<math> \sum_{i=1}^{2^{r-1}-1}t^{d_i}</math>),
where 2<sup>r</sup> d<sub>i</sub>=(2<sup>m</sup>-1)i+2<sup>r</sup> and aβˆˆπ”½<sub>2<sup>n</sup></sub> is such that
where 2<sup>r</sup> d<sub>i</sub>=(2<sup>m</sup>-1)i+2<sup>r</sup> and aβˆˆπ”½<sub>2<sup>m</sup></sub> is such that
a+a<sup>2<sup>m</sup></sup>β‰  0. Β 
a+a<sup>2<sup>m</sup></sup>β‰  0. Β 
This function has algebraic degree r+1Β  and belongs to the completed
This function has algebraic degree r+1Β  and belongs to the completed
Maiorana-McFarland class.
Maiorana-McFarland class.

Latest revision as of 16:34, 4 March 2020

Background and Definitions

Definition. A power boolean function π‘₯𝑑 defined on 𝔽2𝑛 is called a Niho power function, if its restriction to 𝔽2m is linear, where n=2m.

Niho bent functions are bent functions with Niho exponents.

Niho bent functions in bivariant form: [math]\displaystyle{ g(x,y)= \left\{ \begin{aligned} Tr_m\Big(xG\Big(\frac{y}{x}\Big)\Big), & \text{ if } x\neq 0; \\ Tr_m(\mu y), & \text{ if } x=0, \end{aligned} \right. }[/math]

where μ∈ 𝔽2m, 𝐺 :𝔽2m β†’ 𝔽2m satisfying the following conditions:

𝐹 : 𝑧 β†’ G(𝑧)+μ𝑧 is a permutation over 𝔽2m, (1)

z →𝐹(𝑧)+β𝑧 is 2-to-1 on 𝔽2m for any nonzero Ξ²βˆˆπ”½2m . (2)


Here condition (2) implies condition (1) and it is necessary and suffcient for g being bent.

One can get a univariate representation of Niho bent function from bivariant one making the following substitutions: x=t+t2m and y=Ξ±t +(Ξ±t)2m, where Ξ± is a primitive element of 𝔽2m .

Examples

The known Niho type bent functions in univariant form

1. Quadratic function Trm (π‘Žπ‘‘2π‘š+1), where π‘Žβˆˆπ”½2m.

2. Binomials of the form 𝑓(𝑑)= Trn(Ξ±1𝑑𝑑1+Ξ±2𝑑𝑑1),where

2𝑑1≑ 2m1+1 mod(2n-1) and Ξ±1, Ξ±2βˆˆπ”½*2n are such that (Ξ±1+Ξ±12m)2=Ξ±22m+1. These functions have algebraic degree m and do not belong to the completed Maiorana-McFarland class.

3. Let 1 < r < m with gcd(r,m) = 1,

𝑓(𝑑)= Trn(a2t2m+1+(a+a2m)[math]\displaystyle{ \sum_{i=1}^{2^{r-1}-1}t^{d_i} }[/math]),

where 2r di=(2m-1)i+2r and aβˆˆπ”½2n is such that a+a2mβ‰  0. This function has algebraic degree r+1 and belongs to the completed Maiorana-McFarland class.