Cryptography Reference
In-Depth Information
By using the Bonferroni inequality [Com74, p. 193] on the probability of the
union of events we obtain
prob
x
∈X
E
x
≥
prob
(
E
x
)
−
prob
(
E
x
∩
E
y
)
(16)
x
∈X
{
x
,
y
}⊂X
m
(
m
−
1)
q
2
≥
mq
−
(17)
2
m
2
q
2
2
≥
mq
−
≥
mq
(1
−
mq/
2)
,
where (17) follows from Lemma 1. This bound is rather sharp for small values
of
mq
. On the other hand for larger values of
mq
, another lower bound on
prob
(
X
∩ C
rand
=
∅
) is more suitable [dC97]. It gives
prob
x
∈X
prob
(
E
x
)
2
y
∈X
prob
(
E
x
∩
E
x
≥
(18)
E
y
)
x
∈X
mq
2
q
+(
m
≥
(19)
−
1)
q
2
mq
2
q
+
mq
2
≥
(20)
1
1+
≥
1
mq
1
mq
,
≥
1
−
By taking the maximum of both lower bounds, we obtain our lemma.
5.2 Estimating the Complexity of Algorithm 1
Here we estimate how many iterations have to be performed in order to break
the scheme when no signature is known and when
S
=[1
N
]. For this purpose,
we start by lower-bounding the probability that an iteration is successful. Let
us bring the following random variables for
i
···
∈{
1
,
2
}
:
de
=
I
i
∩
W
i
de
=
I
i
I
i
|
J
and
|
.
By using Lemma 1, we know that an iteration finds a valid signature when there
is an
x
in
C
sec
such that
|
x
I
1
|
=
|
x
I
2
|
=
p.
