APN mappings over GF(2,6)

Transkript

Zülfükar Saygı
TOBB ETU
 Haziran 
Zülfükar Saygı (TOBB ETU)
1 / 27
subject of the talk
A brief description of the classification of the APN cubics in 6
variables that is a joint work with
Elif Saygı,
Philippe Langevin.
2 / 27
subject of the talk
A brief description of the classification of the APN cubics in 6
variables that is a joint work with
Elif Saygı,
Philippe Langevin.
The details of this 2011/12 computational project are available :
langevin.univ-tln.fr/project
This talk is presented by Philippe Langevin in YACC 12,
September 24 – September 28, 2012, Porquerolles Island, France
2 / 27
definition
m a positive integer,
F2 finite field of order 2.
m
f : Fm
2 → F2
(
u
Nf (u, v ) := #
v
= x + y;
= f (x) + f (y ).
3 / 27
definition
m a positive integer,
F2 finite field of order 2.
m
f : Fm
2 → F2
(
u
Nf (u, v ) := #
v
= x + y;
= f (x) + f (y ).
u 6= 0 =⇒ Nf (u, v ) = 0 or 2
[APN] almost perfect non-linear.
3 / 27
cube map
Fm
2 additive structure of F2m
(q = 2m )
f : x 7→ x 3 = x 2 x
4 / 27
cube map
Fm
(q = 2m )
f : x 7→ x 3 = x 2 x
f (x + u) + f (x) = (x + u)3 + x 3
= ux 2 + u 2 x + u 3
4 / 27
cube map
Fm
(q = 2m )
f : x 7→ x 3 = x 2 x
f (x + u) + f (x) = (x + u)3 + x 3
= ux 2 + u 2 x + u 3
As a vectorial function, the cube map is quadratic !
4 / 27
affine equivalence
Let A, B, C three affine transformations of Fm
2 . If A, B are
permutations then
f is APN ⇐⇒ A ◦ f ◦ B + C is APN
notation :
aff
f ∼g
same definition for (m, n) − mappings
5 / 27
flat characterization
[APN]
(
x +y +z +t =0
all distinct
=⇒ f (x) + f (y ) + f (z) + f (t) 6= 0
6 / 27
code characterization


1 ... 1 ... 1
... 1 
Hf =  0 . . . x
f (0) . . . f (x) . . . f (1)
[APN] the minimal distance of code(f ) is greater than 4.
(The code is double-error-correcting (no fewer than 5 cols sum to 0).)
7 / 27
ccz-equivalence
In particular, if
code(f ) ∼ code(g )
then one denotes
ccz
f ∼g
same definition for (m, n) − mappings
8 / 27
ccz-quadraticity
There are some constructions of APN mappings, mainly :
quadratic
power mappings : Gold, Kasami, . . .
In dimension 6, all of these are ccz-equivalent to a quadratic
mapping ! ?
9 / 27
ccz-quadraticity
[2009] Dillon discovered an APN permutation of F62 , it is
ccz-quadratic.
The only known example in even dimension.
[2009] Edel and Pott discovered a nice cubic APN in dimension 6
wich is not ccz-quadratic.
The only example in dimension 6.
10 / 27
small dimensions
All the APNs are known, for m= 1, 2, 3, 4, 5 :
[m=4] 1 ccz-class, 2 affine class.
[m=5] 3 ccz-class, 7 affine class.
[2007] Brinkmann and Leander computed the ccz-classification of
maps in dimension 5.
two weeks of computation !
Our approach enable us to ccz-classify the APN maps in less
than two hours.
11 / 27
open numerical questions
12 + 1 + 1 ccz-class of APNs are known.
APNs is a small set in a huge space . . .
is it possible to ccz-classify of all APN in dimension 6 ?
12 / 27
It looks hard !
affine classification of all APN cubics in dimension 6 ?
12 / 27
It looks hard !
affine classification of all APN cubics in dimension 6 ?
Indeed, it is feasible. We find a way that runs in about two months.
12 / 27
ambient spaces
dim Boolean cubics = 1 + 6 + 15 + 20 = 7 + 35
The space of vectorial cubics
42 ∗ 6 = 252
For APN, we do not care about linear terms
35 ∗ 6 = 210
In general, 4 components are enough
35 ∗ 4 = 140
13 / 27
terminology
An affine classification of the set of APNs is a set X such that
∀f ∈ apn(m),
∃!g ∈ X ,
aff
g ∼ f.
A covering at level n, is a set of (m, n)-maps Y such that :
∀f ∈ apn(m),
∃g ∈ Y ,
∃h,
aff
(g , h) ∼ f .
It is convenient to reduce covering sets ! We need to test affine
equivalence of (m, n)-mappings.
14 / 27
classification steps
15 / 27
Boolean cubics
The first important step is to classify the Boolean cubics in
dimension 6 under the action of the affine group agl(6) :
34 class
dimension 35
We use computational algebra methods to keep in memory :
representative
orbit size
fixator group
Note that we plan to use about 32 Gb of shared memory
16 / 27
coordinate, component space
n
Consider (m, n)-mappings i.e. Fm
2 7→ F2
f = (f1 , f2 , . . . , fn )
where fi are Boolean functions.
∀λ ∈ Fn2 ,
def
fλ =
n
X
λi fi
i=1
component space :
vect(f ) = hf1 , f2 , . . . , fn i
[APN] a m-space on which the “affine” characters are not trivial.
f 7→ χ(f ) = µ(f (x) + f (y ) + f (z) + f (t))
17 / 27
invariants
invariant :
[class(s) | s ∈ vect(f )]sorted
representative :
In order to construct a “canonical” representative, we select the type
of cubic that appears in vect(f ) that minimizes ]fix(s).
Then it is possible to deduce the smallest value of
[vect(g )]sorted
aff
where r ∈ vect(g ) and g ∼ f .
18 / 27
Walsh coefficients
Let f be a Boolean function.
X
X
b
f (a) =
(−1)f (x)+a.x =
(−1)f (x) µa (x)
x∈Fm
2
x∈Fm
2
19 / 27
Walsh coefficients
Let f be a Boolean function.
X
X
b
f (a) =
(−1)f (x)+a.x =
(−1)f (x) µa (x)
x∈Fm
2
Nf (u, v ) =
x∈Fm
2
1 XXb 2
fλ (a) µa (u)µb (v )
22m a∈Fm λ∈Fn
2
2
19 / 27
Walsh moment
[APN]
X
fbλ (a)4 = 2q 3 (q − 1),
(1)
def
b
f (a)4 , L(bent) = q 3 , L(f ) = α(f )q 3 .
X
L(fλ ) = 2q 3 (q − 1),
(2)
a,06=λ∈Fm
2
L(f ) =
P
a∈Fm
2
06=λ∈Fm
2
It exists a component such that
L(fλ ) ≤ 2q 3 ,
i.e. α(fλ ) ≤ 2
(3)
20 / 27
classification of Boolean cubics
Type
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ANF of Representative
ace + bce + bde + bcf + adf
ab + ace + bce + bde + bcf + adf
ab + cd + ace + bce + bde + bcf + adf
cde + abf
ac + cde + abf
bc + ad + cde + abf
bd + ae + cde + abf + cf
bcd + ace + abf
ad + bcd + ace + abf
ad + bcd + be + ace + abf
bd + cd + bcd + ce + ace + abf
bcd + ace + de + abf
ad + bd + cd + bcd + be + ce + ace + abf + cf
bcd + ace + de + abf + cf
acd + abe
bc + acd + abe
cd + acd + abe
α
3, 8125
3, 0625
2, 3125
7, 5625
4, 5625
3, 0625
2, 3125
5, 5
4
2, 5
4
3, 25
1
2, 5
11, 5
5, 5
7
21 / 27
classification of Boolean cubics
Type
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
ANF of Representative
bd + cd + acd + abe + ce
acd + abe + af
bc + acd + abe + af
cd + acd + abe + af
bd + cd + acd + abe + ce + af
acd + abe + bf
acd + abe + ce + bf
abc
abc + ad
abc + bd + ae
abc + de
abc + cd + be + af
abc + de + af
0
ab
bc + ad
cd + be + af
α
4
8, 5
2, 5
4
1
4
2, 5
22
10
4
5, 5
1
2, 5
64
16
4
1
22 / 27
extension
Given a candidate at level n,
g = (g1 , g2 , . . . , gn , hn+1 , . . . , hm )
We denote by S = hg1 , g2 , . . . , gn i and V = hhn+1 , . . . , hm i
X
L(t, S) =
L(h).
06=h∈t+S
Assuming (g , h) is an APN-extension
X
L(t, S) = 2q 3 (q − 1),
t∈V
It exists t such that
L(t, S) ≤
2q 3 − L(0, S)
2m−n − 1
23 / 27
extension
It exists t s. t.
L(t, S) ≤
2q 3 − L(0, S)
2m−n − 1
(4)
But, in fact :
t + S contains a bent function !
For all g at level n, we select all the bent functions t satisfying (4).
Indeed the set of bent functions is rather small.
24 / 27
backtracking
Given an (m, n)-mapping g .
can we extend g as an APN ?
Does there exist a (m, m − n)-mapping such that :
g (x) + g (y ) + g (z) + g (t) = 0 =⇒ h(x) + h(y ) + h(z) + h(t) 6= 0?
We use backtracking to solve it.
It works well for (5, 3) and (6, 4) mappings.
25 / 27
dancing links
26 / 27
output
At the end, we get
534 affine class of APN cubics
14 ccz-class
27 / 27

APN mappings over GF(2,6)

Transkript

Benzer belgeler

Read More - Palmarina Bodrum

read detailed cover letters. - Mechanical Engineering

PROF. DR. İBRAHİM DENİZ AKÇALI YAZIŞMA

05_12_05_2015_lista PDF EZ_SDI20 sito_en.xlsx

Ders Dosyası

A A

Studien*) zu Indikationen: Schmerzen A systematic

CS473-Algorithms I - Bilkent University Computer Engineering

n - Bilkent University Computer Engineering Department