Cryptography Reference
In-Depth Information
µ
(
n
))
p
(
n
)
<
0
.
01 for every polynomial
p
and suciently big
n
(i.e.,
µ
is negligible if for every positive polynomial
p
the function
µ
(
if 1
−
(1
−
) is upper-bounded by 1
/p
(
)). However, if we consider the function
T
(
n
) to provide our notion of infeasible computation then functions
bounded above by 1
/T
(
n
) are considered negligible (in
n
).
We will also refer to the notion of
noticeable probability
.Herethe
requirement is that events that occur with noticeable probability, will
occur almost surely (i.e., except with negligible probability) if we repeat
the experiment for a polynomial number of times. Thus, a function
ν
:
·
·
is called
noticeable
if for some positive polynomial
p
the
N
→
N
) is lower-bounded by 1
/p
(
function
ν
(
·
·
).
