Introduction and Preliminaries - Foundations of Cryptography-A Primer - page 8

regarding the computational resources of the adversary, where we refer
tothenotionoffeasiblethatwewishtobeaswideaspossible.Acom-
mon approach is to postulate that feasible computations are polynomial-
time too, but here the polynomial is not a-priori specified (and is to
be thought of as arbitrarily large). In other words, the adversary is
restricted to the class of polynomial-time computations and anything
beyond this is considered to be infeasible .
Although many definitions explicitly refer to the convention of asso-
ciating feasible computations with polynomial-time ones, this conven-
tion is inessential to any of the results known in the area. In all cases,
a more general statement can be made by referring to a general notion
of feasibility, which should be preserved under standard algorithmic
composition, yielding theories that refer to adversaries of running-time
bounded by any specific super-polynomial function (or class of func-
tions). Still, for sake of concreteness and clarity, we shall use the former
convention in our formal definitions (but our motivational discussions
will refer to an unspecified notion of feasibility that covers at least
ecient computations).

Randomized (or probabilistic) computations

Randomized computations play a central role in cryptography. One
fundamental reason for this fact is that randomness is essential for
the existence (or rather the generation) of secrets. Thus, we must allow
the legitimate users to employ randomized computations, and certainly
(since randomization is feasible) we must consider also adversaries that
employ randomized computations. This brings up the issue of success
probability: typically, we require that legitimate users succeed (in ful-
filling their legitimate goals) with probability 1 (or negligibly close to
this), whereas adversaries succeed (in violating the security features)
with negligible probability. Thus, the notion of a negligible probability
plays an important role in our exposition. One requirement of the defi-
nition of negligible probability is to provide a robust notion of rareness:
A rare event should occur rarely even if we repeat the experiment for a
feasible number of times. That is, in case we consider any polynomial-
time computation to be feasible, a function µ :

N → N

is called negligible