Cryptography Reference
In-Depth Information
Impact of the Variations of
p
.
The optimal value of
p
for large
N
might not be
thesameasfor
N
= 1. In practice when
(
p,
1
) vary slowly with
p
(parameters
corresponding to encryption) the behavior of Proposition 3 can be extended to
the workfactor and, as long as
N
is not too large, we have
T
ISD
(
n,r,w
)=
WF
ISD
(
n,r,w
)
1
2
−
w − p
r −
1
−
w−p−
1
2
WF
(
N
)
where
γ ≈
0
.
721
(10)
N
γ
where
p
and
1
are the optimal parameters of the algorithm when
N
=1.For
parameters corresponding to digital signature and hash function, the algorithm
does not seem to take full benefit of multiple instances.
Tabl e 5.
Decoding
N
instances
log
2
N p
WF
(
N
)
(
n, r, w
)
observed
γ
expected
γ
ISD
(4096
,
540
,
45)
0
12 60 128
.
4
−
−
(4096
,
540
,
45)
40
12 80 110
.
5
0
.
4486
0
.
4487
(4096
,
540
,
45) 83
.
7 10 94
91
.
6
0
.
4398
0
.
4487
(2048
,
352
,
32)
0
6 30
81
.
0
−
−
(2048
,
352
,
32)
40
7 54
63
.
4
0
.
4403
0
.
4394
(2048
,
352
,
32) 51
.
4 7 60
58
.
8
0
.
4324
0
.
4394
(2
20
,
180
,
11)
0
10 94
87
.
8
−
−
(2
20
,
180
,
11)
40
6 79
79
.
6
0
.
2038
0
.
4856
(2
20
,
180
,
11)
70
.
3 4 76
74
.
6
0
.
1875
0
.
4856
(2
21
,
1024
,
256)
0
16 144 144
.
0
−
−
(2
21
,
1024
,
256)
40
6 79 141
.
5
0
.
0640
0
.
2724
(2
21
,
1024
,
256) 117
.
6 4 76 137
.
1
0
.
0597
0
.
2724
5.3 Unlimited Number of Instances
We assume that the attacker can let
N
grow indefinitely. Because any algorithm
must at least read its input there is a limit to the growth of
N
. By “unlimited”
we mean that the attacker has reached this limit (whatever it is). We will denote
WF
(
∞
)
ISD
(
n,r,w
)=min
N,p,
T
N
(
p,
)
and we wish to compare this cost with WF
ISD
(
n,r,w
). The best strategy for the
attacker is to take a number of instances equal to
=
min
2
r
,
w
1
ε
(
p,
)
k
+
p
N
=
r−
w−p
k
+
p
in which case (assuming
K
0
= 0, see the discussion in
§
5.1) the complexity is
T
∞
(
p,
)=
2
√
K
1
K
2
K
3
2
ε
(
p,
)
ε
(
p,
)
+
