Cryptography Reference
In-Depth Information
Probability Rules
The Difference Rule
s
, then
p
s
s
=
p
s
−
If
s
⊆
p
s
.
The Sum Rule
p
s
∪
s
=
p
s
+
p
s
−
p
s
∩
s
.
The Product Rule
If
p
s
>
0, then
p
s
∩
s
=
p
s
|
s
·
p
s
.
Moreover, if
s
and
s
are independent, then
p
s
∩
s
=
p
s
·
p
s
.
There is a well-known result that is merely the putting together of some of
the above facts.
Baye's Theorem
If
s
∈
S
and
t
∈
T
are events such that
p
S
(
s
)
>
0 and
p
t
>
0, then
p
s
|
t
=
p
s
·
p
t
|
s
p
t
.
Baye's theorem allows us to formulate the conditional probability of
s
given
t
in terms of the conditional probability of
t
given
s
. This is a valuable tool in
Chapter 11, when we talk about entropy.
Another question of importance in probability is: What is the probability
that after
n
trials of some experiment at least two of the outcomes are the same?
For instance, see the birthday attack on page 252.
Probability of Two Outcomes Being the Same
Let
S
be an experiment that is the choice of an element from
S
(without
removing it from
S
), with outcomes
having equal probabil-
ities
p
s
j
=1
/m
for all
j
=1
,
2
,...,m
. Then the probability of two outcomes
being the same after
n
trials is at least
S
=
{
s
1
,s
2
,...,s
m
}
e
−
(
n
−
1)
n/
(2
m
)
.
1
−
We see from this fact that if
n>
√
2
m
ln 2, then the probability that at least
two outcomes will be the same is at least 50%. (See page 254 for a comparison
with the birthday attack.)
Search WWH ::
Custom Search