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