Cryptography Reference
In-Depth Information
error probability (i.e.,
δ
) can be made negligible (as a function in
n
), but the accuracy of
the estimation (i.e.,
) can be bounded above only by any fixed polynomial fraction (but
cannot be made negligible).
2
We stress that the dependence of the number of samples
on
ε
is not better than in the case of pairwise-independent sampling; the advantage of
totally independent samples lies only in the dependence of the number of samples on
ε
.
A more general bound, useful for approximation of the expectation of a general
random variable (not necessarily 0-1), is given as follows:
δ
Hoefding Inequality:
3
Let X
1
,
X
2
,...,
X
n
be n independent random variables
with the same probability distribution, each ranging over the (real) interval
[
a
,
b
]
,
and let
µ
denote the expected value of each of these variables. Then, for every
ε>
0
,
i
=
1
X
i
n
>ε
2
2
ε
·
e
−
·
n
Pr
−
µ
<
2
a
)
2
(
b
−
The Hoefding inequality is useful for estimating the average value of a function defined
over a large set of values, especially when the desired error probability needs to be
negligible. It can be applied provided we can efficiently sample the set and have a
bound on the possible values (of the function). See Exercise 2.
1.3. The Computational Model
Our approach to cryptography is heavily based on computational complexity. Thus,
some background on computational complexity is required for our discussion of cryp-
tography. In this section, we briefly recall the definitions of the complexity classes
P
,
NP
poly) and the concept of oracle machines.
In addition, we discuss the types of intractability assumptions used throughout the rest
of this topic.
,
BPP
, and “non-uniform
P
” (i.e.,
P
/
P
NP
NP
-Completeness
A conservative approach to computing devices associates efficient computations with
the complexity class
1.3.1.
,
, and
. Jumping ahead, we note that the approach taken in this topic
is a more liberal one in that it allows the computing devices to be randomized.
P
Definition 1.3.1 (Complexity Class
):
A language L is
recognizable in
(deter-
ministic)
polynomial time
if there exists a deterministic Turing machine M and
a polynomial p
(
P
·
)
such that
on input a string x , machine M halts after at most p
(
|
x
|
)
steps, and
M
(
x
)
=
1
if and only if x
∈
L.
2
Here and in the rest of this topic, we denote by poly() some fixed but unspecified polynomial.
3
A more general form requires the
X
i
's to be independent, but not necessarily identical, and uses
n
i
=
1
E
(
X
i
). See [6, app. A].
def
=
1
µ
