Cryptography Reference
In-Depth Information
ω
elementary event
n
U
n
uniform probability distribution on
{
0
,
1
}
A
event
A
complement of event
A
Pr
probability measure
Pr[
A
]
probability of event
A
Pr[
ω
|A
]
conditional probability of
ω
given that
A
holds
Pr[
A|B
]
conditional probability of
A
given that
B
holds
X
random variable
P
X
probability distribution of
X
P
XY
joint probability distribution of
X
and
Y
P
X
1
...X
n
joint probability distribution of
X
1
,...,X
n
P
X|A
conditional probability distribution of
X
given that
A
holds
P
X|Y
conditional probability distribution of
X
given that
Y
holds
E
[
X
]
expectation (or mean) of
X
E
[
X
|A
]
conditional expected value of
X
given that
A
holds
Var
[
X
]
variance of
X
σ
[
X
]
standard deviation of
X
H
(
X
)
entropy of
X
H
(
XY
)
joint entropy of
X
and
Y
H
(
X
|
Y
=
y
)
conditional entropy of
X
when
Y
=
y
H
(
X
|
Y
)
conditional entropy of
X
when given
Y
I
(
X
;
Y
)
mutual information between
X
and
Y
H
L
entropy of language
L
R
L
redundancy of language
L
n
u
unicity distance
M
Turing machine
S
M
space complexity of Turing machine
M
T
M
time complexity of Turing machine
M
P
“polynomial-time” complexity class
NP
,co
NP
“nondeterministic polynomial-time” complexity classes
PP
“probabilistic polynomial-time” complexity class
ZPP
“zero-sided error probabilistic polynomial-time” complexity class
PP
-Monte Carlo and
PP
-Las Vegas
“one-sided error probabilistic polynomial-time” complexity classes
BPP
“bounded-error probabilistic polynomial-time” complexity class
A
f
distinguisher
A
that is given oracle access to function
f
O
P
oracle for problem
P
M
(plaintext) message space
C
ciphertext space
