Cryptography Reference
In-Depth Information
and the gain we wish to estimate is the ratio
WF
ISD
(
n,r,w
)
WF
(
N
)
γ
=log
N
ISD
(
n,r,w
)
which we expect to be close to 1
/
2. First, we must have
=
min
2
r
,
w
1
ε
(
p,
)
k
+
p
N ≤
r−
w−p
k
+
p
else there is nothing to gain. Within this bound, we have
P
N
(
p,
)=
Nε
(
p,
)
k
+
p
L
N
(
p,
)=
K
2
K
1
N
k
+
p
and
and (assuming
K
0
=0)
2
√
K
1
K
2
N
k
+
p
K
3
2
ε
(
p,
)
.
T
N
(
p,
)=
+
ε
(
p,
)
Thesameanalysisasin
4.1 will tell us that the above sum is minimal (up to a
factor at most two) when its two terms are equal, that is when
=
N
(
p
), or
N
for short, where
§
K
3
N
k
+
N
p
⎛
⎞
⎝
⎠
.
N
=log
2
2
√
K
1
K
2
Proposition 3.
For a given
p
, we have
T
N
(
p,
N
)
=
1
T
(
p,
1
)
1
2ln2
w − p
r −
1
−
w−p−
1
log
N
2
− c
(
p
)
where
c
(
p
)
≈
.
2
Proof.
We have
K
3
N
k
+
N
p
K
3
k
+
1
p
⎛
⎞
⎛
⎞
⎝
⎠
and
1
=log
2
⎝
⎠
N
=log
2
2
√
K
1
K
2
2
√
K
1
K
2
and if we consider only the first order variations, we have
N
≈
1
+
2
log
2
N
.
Because we have
a
b
=
a
b
Δ
(
a, b
)where
Δ
(
a, b
)=
b−
1
d
da
1
a − i
≈
b
a −
b−
1
2
i
=0
it follows that, keeping only the first order variations, we have
ε
(
p,
N
)=
ε
(
p,
1
)exp(
−c
(
p
)log
N
)
where
c
(
p
)
≈ Δ
(
r −
1
,w− p
)
/
2 ln(2). Finally
T
=
√
N
exp(
T
N
(
p,
N
)
=
2
N
ε
(
p,
N
)
(
p,
1
)
−c
(
p
)log
N
)
.
2
1
ε
(
p,
1
)
