Cryptography Reference
In-Depth Information
practical construction of Y. At the very least, such a result can be viewed as a challenge
to the researchers to either provide a practical construction of Y using X or explain why
a practical construction cannot be provided.
A result of the second type says that any task that belongs to some class
is solvable,
but the generic construction provided in the proof may be impractical. Still, this is a very
valuable piece of information: If we have a specific problem that falls into the foregoing
class, then we know that the problem is solvable in principle. However, if we need to
construct a real system, then we probably should construct a solution from scratch (rather
than employing the preceding generic result).
To summarize, in both cases a plausibility result provides very useful information
(even if it does not yield a practical solution). Furthermore, it is often the case that some
tools developed toward proving a plausibility result may be useful in solving the specific
problem at hand. This is typically the case for the next type of results.
2. Introduction of paradigms and techniques that may be applicable in practice: Here we
refer to results that are aimed at introducing a new notion, model, tool, or technique.
Such results (e.g., techniques) typically are applicable in practice, either as presented in
the original work or, after further refinements, or at least as an inspiration.
3. Presentation of schemes that are suitable for practical applications.
C
Typically, it is quite easy to determine to which of the foregoing categories a specific
result belongs. Unfortunately, the classification is not always stated in the original pa-
per; however, typically it is evident from the construction. We stress that all results of
which we are aware (in particular, all results mentioned in this topic) come with an
explicit construction. Furthermore, the security of the resulting construction is explic-
itly related to the complexity of certain intractable tasks. Contrary to some uninformed
beliefs, for each of these results there is an explicit translation of concrete intractability
assumptions (on which the scheme is based) into lower bounds on the amount of work
required to violate the security of the resulting scheme. 9 We stress that this translation
can be invoked for any value of the security parameter. Doing so will determine whether
a specific construction is adequate for a specific application under specific reasonable
intractability assumptions. In many cases the answer is in the affirmative, but in general
this does depend on the specific construction, as well as on the specific value of the
security parameter and on what it is reasonable to assume for this value (of the security
parameter).
1.4.3. The Tendency to Be Conservative
When reaching the chapters in which cryptographic primitives are defined, the reader
may notice that we are unrealistically “conservative” in our definitions of security.
In other words, we are unrealistically liberal in our definition of insecurity. Techni-
cally speaking, this tendency raises no problems, because our primitives that are secure
in a very strong sense certainly are also secure in the (more restricted) reasonable
sense. Furthermore, we are able to implement such (strongly secure) primitives using
9 The only exception to the latter statement is Levin's observation regarding the existence of a universal one-way
function (see Section 2.4.1).
Search WWH ::




Custom Search