Cryptography Reference
In-Depth Information
The minimal value is reached, up to a constant factor, when
=
∞
(
p
) such that
K
3
2
K
1
K
2
ε
(
p,
∞
(
p
))
∞
(
p
) = log
2
.
Interestingly
∞
(
p
) is increasing with
p
and so is the complexity
(
p,
∞
(
p
)).
We thus want to choose
p
as small as possible. On the other hand, we have
|W
1
||W
2
|
T
=
k
+
p
and
|W
2
|
must be a positive integer which limits the decrease
of
p
.Wemusthave
k
+
p
k
+
p
,
K
2
K
1
ε
(
p,
)
≤
|W
1
|≤
⇒
with equality for the optimal
p
. Finally the optimal pair (
p,
) is the unique one
such that we have simultaneously
⎛
⎞
⎠
=log
2
K
3
2
K
2
min
2
r
,
w
k
+
p
.
K
3
2
√
K
1
K
2
⎝
=log
2
r−
w−p
An Estimate of the Improvement.
Let
p
is the optimal value obtained
above with an unlimited number of instances. In that case (we take
K
0
=0,
K
1
=
K
2
=1,
K
3
=2)
k
+
1
p
and
∞
=log
2
k
+
∞
.
1
=log
2
p
Keeping the first order variations we have
∞
≈
2
1
. From Proposition 3 we have
T
(
p,
1
)
0
.
721
w − p
r −
1
T
∞
(
p,
∞
)
=
1
log
2
− c
(
p
)where
c
(
p
)
≈
N
≈T
∞
(
p,
∞
)
2
−c
(
p
)
2
∞
.Thus
where
N ≈T
∞
(
p,
∞
)
≈
T
(
p,
1
)
Proposition 4.
For a given
p
, we have
log
T
∞
(
p,
∞
)
=
2
T
(
p,
1
)
3
+
4
1
2ln2
w − p
r −
1
−
w−p−
1
2
9
c
(
p
)
where
c
(
p
)
≈
.
log
Coming back to the single instance case, and assuming that
T
(
p,
1
) varies very
slowly with
p
, we may assume that WF
ISD
(
n,r,w
)
(
p,
1
). This means that
when an attacker has access to an unlimited number of instances and needs to
decode one of them only, the decoding exponent is multiplied by a quantity,
slightly larger than 2
/
3, close to the one given in the above proposition.
≈T
w − p
r −
1
−
w−p−
1
2
2
3
+0
.
321
WF
(
∞
)
ISD
(
n,r,w
)=WF
ISD
(
n,r,w
)
β
where
β ≈
(11)
where
p
and
1
are the optimal parameters of the algorithm when
N
=1.