Cryptography Reference
In-Depth Information
Therefore the probability of success
P
succ
is lower bounded by
P
succ
≥
prob
(
W
1
=
w
1
,W
2
=
w
2
)
(21)
w
1
,w
2
:
w
1
+
w
2
n
=
x
I
2
|
prob
∃
x
∈ C
sec
:
W
1
=
w
1
,W
2
=
w
2
|
x
I
1
|
=
p
|
On the other hand, by using Lemma 3 with the set
X
de
=
x
=
x
I
2
|
=
p
=(
x
j
)
j∈J
:
|
x
I
1
|
which is of size
w
p
w
p
2
n−w
1
−w
2
,weobtain
prob
∃
x
∈ C
sec
:
=
x
I
2
|
W
1
=
w
1
,W
2
=
w
2
≥
|
x
I
1
|
=
p
|
f
(
x
)
.
(22)
with
w
p
w
p
2
n−w
1
−w
2
2
n−k
=
w
1
p
w
2
p
2
k−w
1
−w
2
x
de
=
The first quantity is clearly equal to
prob
(
W
1
=
w
1
,W
2
=
w
2
)=
w
1
n−w
1
N−n
(
K
+
k
+
l
)
/
2
N−n−
(
K
+
k
+
l
)
/
2+
w
1
(
K
+
k
+
l
)
/
2
w
2
−w
1
−w
2
.
(
K
+
k
+
l
)
/
2
N−
(
K
+
k
+
l
)
/
2
(
K
+
k
+
l
)
/
2
N
(23)
Plugging in the expressions obtained in (22) and (23) in (21) we have an explicit
expression of a lower bound on
P
succ
. The number of iterations for our attack
to be successful is estimated to be of order
1
P
succ
. We obtain therefore an upper-
bound on the expected number of iterations, what we denote by
UpperBound
.
Table 2 shows for various KKS parameters,
p
and
l
the expected number of
iterations.
1
P
succ
Table 2.
KKS Parameters with the corresponding value of
p n
de
=
E
{|I
|}
Article
ρ
n
l
R
N
UpperBound
60
1023
≈
0
.
059 1,023 8
192
3000
≈
0
.
064 3,000
[KKS97]
1
91
111
.
26
60
1023
≈
0
.
059 1,023 14 2
192
3000
≈
0
.
064 3,000
14
.
17
91
48
255
≈
0
.
188 255
273
1200
≈
0
.
228 1,200
[KKS05]
8
1
66
26
.
41
48
255
≈
0
.
188 255
273
1200
≈
0
.
228 1,200
14 2
66
4
.
37
48
180
≈
0
.
267 180
335
1100
≈
0
.
305 1,100
[KKS97]
8
1
65
6
.
07
48
180
≈
0
.
267 180
335
1100
≈
0
.
305 1,100
15 2
65
1
.
82
[BMJ11]
1
/
2
320
12 1
165
1
/
2
11,626
1
.
24
[BMJ11]
1
/
2
448
13 1
230
1
/
2
16,294
1
.
34
[BMJ11]
1
/
2
512
13 1
264
1
/
2
18,586
1
.
39
1
/
2
1
/
2
1
.
61
[BMJ11]
768
13 1
395
27,994
[BMJ11]
1
/
2
1,024 14 1
527
1
/
2
37,274
1
.
85
