Cryptography Reference
In-Depth Information
Chapter 4
Probability Theory
Probability theory plays a central role in information theory and contemporary
cryptography. In fact, the ultimate goal of a cryptographer is to make the probability
that an attack against the security of a cryptographic system succeeds equal—or
at least close—to zero. Probability theory provides the formalism for this kind of
reasoning.
In this chapter, we introduce and overview the basic principles of (discrete)
probability theory as far as they are relevant for information theory and contempo-
rary cryptography. More specifically, we introduce basic terms and concepts in Sec-
tion 4.1, elaborate on random variables in Section 4.2, and conclude with some final
remarks in Section 4.3. The chapter is intentionally kept short; further information
can be found in any textbook on probability theory (e.g., [1-4]).
4.1
BASIC TERMS AND CONCEPTS
The notion of a discrete probability space as formally introduced in Definiton 4.1
is at the core of probability theory and its application in information theory and
contemporary cryptography.
Definition 4.1 (Discrete probability space)
A
discrete probability space
1
consists
of a finite or countably infinite set
Ω
called the
sample space
and a probability
measure
Pr : Ω
+
with
ω∈
Ω
Pr[
ω
]=1
.
2
−→
R
The elements of the sample space Ω are called
simple events
,
indecomposable
events
, or—as used in this topic—
elementary events
.
1
In some literature, a discrete probability space is called a
discrete random experiment
.
2
Alternative notations for the probability measure Pr[
·
] are P(
·
),P[
·
],orProb[
·
].
