Cryptography Reference
In-Depth Information
1.5.2. Suggestions for Further Reading
The background material concerning probability theory and computational complexity
provided in Sections 1.2 and 1.3, respectively, should suffice for the purposes of this
topic. Still, a reader feeling uncomfortable with any of these areas may want to consult
some standard textbooks on probability theory (e.g., [79]) and computational complex-
ity (e.g., [86; 202]). The reader may also benefit from familiarity with randomized
computation [167; 97, app. B].
Computational problems in number theory have provided popular candidates for
one-way functions (and related intractability assumptions). However, because this topic
focuses on concepts, rather than on specific implementation of such concepts, those
popular candidates will not play a major role in the exposition. Consequently, back-
ground in computational number theory is not really necessary for this topic. Still, a
brief description of relevant facts appears in Appendix A herein, and the interested
reader is referred to other text (e.g., [10]).
This topic focuses on the basic concepts, definitions, and results in cryptography.
As argued earlier, these are of key importance for sound practice. However, practice
needs much more than a sound theoretical framework, whereas this topic makes no
attempt to provide anything beyond the latter. For helpful suggestions concerning prac-
tice (i.e., applied cryptography), the reader may critically consult other texts (e.g.,
[158]).
Our treatment is presented in terms of asymptotic analysis of algorithms. Further-
more, for simplicity, we state results in terms of robustness against polynomial-time
adversaries, rather than discussing general time-bounded adversaries. However, as ex-
plained in Section 1.4, none of these conventions is essential, and the results could be
stated in general terms, as done in Section 2.6 and elsewhere (e.g., [155]). Our choice
to present results in terms of robustness against polynomial-time adversaries makes
the statement of the results somewhat less cumbersome, because it avoids stating the
exact complexity of the reduction by which security is proved. This suffices for stating
plausibility results, which is indeed our main objective in this topic, but when using
schemes in practice one needs to know the exact complexity of the reduction (for that
will determine the actual security of the concrete scheme). We stress that typically it is
easy to determine the complexity of the reductions presented in this topic, and in some
cases we also include comments referring to this aspect. We mention that the alterna-
tive choice, of presenting results in terms of robustness against general time-bounded
adversaries, is taken in Luby's topic [155].
1.5.3. Open Problems
As mentioned earlier (and further formalized in the next chapter), most of the content
of this topic relies on the existence of one-way functions. Currently, we assume the
existence of such functions; it is to be hoped that the new century will witness a proof of
this widely believed assumption/conjecture. We mention that the existence of one-way
functions implies that
NP
is not contained in
BPP
, and thus would establish that
NP = P
(which is the most famous open problem in computer science).
Search WWH ::




Custom Search