Information Technology Reference
In-Depth Information
integers such that
2
−n
(1
−H
2
(
r
n
/n
))
+
H
2
D
n
2
n
=
o
(2
−s
n
)
,
almost all permutations
F
of
F
2
satisfy
nl
s
n
,r
n
(
F
)
>D
n
.
If
s
n
tends to a limit
ρ
≤
.
227
when
n
tends to
∞
and if
r
n
≤
μn
for every
n
,
H
2
(
μ
)
>ρ
(e.g. if
r
n
/s
n
tends to a limit strictly smaller than 1), then
for every
ρ
>ρ
, almost all permutations
F
of
F
2
satisfy
nl
s
n
,r
n
(
F
)
−
where
1
2
(1
−ρ
)
n
.
≥
Proof.
We know (see e.g. [43], page 310) that, for every integer
n
and every
λ
[0
,
1
/
2], we have
i≤λn
i
≤
2
nH
2
(
λ
)
. According to the Stirling formula, we
have also, when
i
and
j
tend to
∞
:
i
!
∼ i
i
e
−i
√
2
πi
and
i
+
j
i
∈
i
+
j
ij
∼
(
i
+
j
i
)
i
(
i
+
j
j
)
j
.
√
2
π
For
i
+
j
=2
n
and
i
=2
n−s
n
,thisgives
2
n
2
n−s
n
(2
s
n
)
2
n−s
n
2
s
n
∼
√
2
π
(1
2
n
−
2
n−s
n
−
2
−s
n
)
2
n
−
2
n−s
n
2
s
n
2
n−sn
√
2
π
2
(2
n
−
2
n−s
n
)ln(1
−
2
−s
n
)log
2
e
2
s
n
=
2
n−s
n
.
2
n
−
We deduce then from inequality (4):
log
2
P
s
n
,r
n
,D
n
=
O
2
n
H
2
D
n
2
n
+2
−n
(1
−H
2
(
s
n
/n
))
+2
−n
(1
−H
2
(
r
n
/n
))
2
−s
n
)log
2
e
2
−s
n
+log
2
(
s
n
)
2
−s
n
(1
−
−
−
s
n
n
2
−s
n
) inside the brackets above since it is neg-
(we omit
−
2
n
+1
+
2
n
+1
log
2
(1
−
ligible).
For
ρ
≤
.
227, we have 1
−
H
2
(
ρ
)
>ρ
and therefore, if asymptotically we
.
227
n
,then2
−n
(1
−H
2
(
s
n
/n
))
is negligible with respect to 2
−s
n
(and
have
s
n
≤
therefore to 2
−s
n
+log
2
(
s
n
)
and to 2
−s
n
(1
2
−s
n
)log
2
e
). This completes the proof
−
that if 2
−n
(1
−H
2
(
r
n
/n
))
+
H
2
D
n
2
n
=
o
(2
−s
n
)and
s
n
≤
.
227
n
, then almost all
permutations
F
of
F
2
satisfy
nl
s
n
,r
n
(
F
)
>D
n
.
If lim
H
2
(
ρ
)
>ρ
and such that asymptotically we have
s
n
≤ ρ
n
; hence 2
−n
(1
−H
2
(
s
n
/n
))
is neg-
ligible with respect to 2
−s
n
.Andif
r
n
≤ μn
where 1
− H
2
(
μ
)
>ρ
,thenwe
have 2
−n
(1
−H
2
(
r
n
/n
))
=
o
(2
−s
n
)andfor
D
n
=2
(1
−ρ
)
n
s
n
.
227 then there exists
ρ
=
ρ
≤
>ρ
such that 1
−
where
ρ
is any number
2
n
=
H
2
2
−ρ
n
=
ρ
n
2
−ρ
n
strictly greater than
ρ
,wehave
H
2
D
n
−
(1
−
2
−ρ
n
)log
2
(1
2
−ρ
n
)=
o
(2
−ρn
)=
o
(2
−s
n
). We obtain that, asymptotically,
nl
s
n
,r
n
(
F
)
>
2
(1
−ρ
)
n
for every
ρ
>ρ
.
−
References
1. Armknecht, F., Carlet, C., Gaborit, P., Kunzli, S., Meier, W., Ruatta, O.: Ecient
computation of algebraic immunity for algebraic and fast algebraic attacks. In:
Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 147-164. Springer,
Heidelberg (2006)
