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
ν
(

·

·

).