Cryptography Reference
In-Depth Information
•A
1
,...,
A
n
are
mutually independent
if for every subset of indices
I
⊆
{
1
,
2
,...,n
}
with
I
=
∅
it holds that
Pr[
i∈I
A
i
]=
Pr[
A
i
]
.
i∈I
Sometimes it is necessary to compute the probability of an elementary event
ω
given that an event
A
with Pr[
A
]
>
0 holds. The resulting
conditional probability
is denoted as Pr[
ω
|A
] and can be computed as follows:
]=
Pr[
ω
]
if
ω
∈A
Pr[
ω
|A
Pr[
A
]
0
otherwise
] must have a value that is proportional to Pr[
ω
],andthe
factor of proportionality must be 1
/
Pr[
If
ω
∈A
,thenPr[
ω
|A
A
] (so that all probabilities sum up to one).
Otherwise (i.e., if
ω/
∈A
), it is impossible that
ω
holds, and hence Pr[
ω
|A
] must be
equal to zero (independent from the probability of
A
).
The definition of Pr[
ω
|A
] can be generalized to arbitrary events. In fact, if
A
and
B
are two events, then the probability of event
B
given that event
A
holds is the
sum of the probabilities of all elementary events
ω
∈B
given that
A
holds. This is
formally expressed as follows:
]=
ω∈B
Pr[
B|A
Pr[
ω
|A
]
In the literature, Pr[
B|A
] is sometimes also defined as follows:
]=
Pr[
A∩B
]
B|A
Pr[
Pr[
A
]
Consequently, if two events
A
and
B
are independent and Pr[
A
]
>
0
(Pr[
B
]
>
0), then Pr[
B|A
]=Pr[
A∩B
]
/
Pr[
A
]=Pr[
A
]
·
Pr[
B
]
/
Pr[
A
]=Pr[
B
]
(Pr[
A|B
]=Pr[
B∩A
]
/
Pr[
B
]=Pr[
B
]
·
Pr[
A
]
/
Pr[
B
]=Pr[
A
]). Put in other words:
if
A
and
B
are independent, then whether
A
holds or not is not influenced by the
knowledge that
B
holds or not, and vice versa. Consequently, one can also write
]=
Pr[
B∩A
]
Pr[
A|B
(4.1)
Pr[
B
]
