Cryptography Reference
In-Depth Information
Practice.
The aim of this primer is to introduce the reader to the
theoretical foundations
of cryptography. As argued above, such founda-
tions are necessary for
sound
practice of cryptography. Indeed, practice
requires more than theoretical foundations, whereas the current primer
makes no attempt to provide anything beyond the latter. However,
given a sound foundation, one can learn and evaluate various prac-
tical suggestions that appear elsewhere (e.g., in (97)). On the other
hand, lack of sound foundations results in inability to critically eval-
uate practical suggestions, which in turn leads to unsound decisions.
Nothing could be more harmful to the design of schemes that need to
withstand adversarial attacks than misconceptions about such attacks.
Non-cryptographic references:
Some “non-cryptographic” works
were referenced for sake of wider perspective. Examples include (4; 5;
6; 7; 55; 69; 78; 96; 118).
1.2
Preliminaries
Modern cryptography, as surveyed here, is concerned with the con-
struction of
ecient
schemes for which it is
infeasible
to violate the
security feature. Thus, we need a notion of ecient computations as
well as a notion of infeasible ones. The computations of the legitimate
users of the scheme ought be ecient, whereas violating the security
features (by an adversary) ought to be infeasible. We stress that we do
not identify feasible computations with ecient ones, but rather view
the former notion as potentially more liberal.
Ecient computations and infeasible ones
E
cient computations
are commonly modeled by computations that are
polynomial-time in the security parameter. The polynomial bounding
the running-time of the legitimate user's strategy is
fixed and typically
explicit
(and
small
). Indeed, our aim is to have a notion of eciency
that is as strict as possible (or, equivalently, develop strategies that are
as ecient as possible). Here (i.e., when referring to the complexity
of the legitimate users) we are in the same situation as in any algo-
rithmic setting. Things are different when referring to our assumptions
