Cryptography Reference
In-Depth Information
required in order to allow a careful examination that may lead either to verification
and justification of our intuition or to its rejection as false (or as something that is true
only in certain cases or only under certain refinements). There are many cases in which
our initial intuition turns out to be correct, as well as many cases in which our initial
intuition turns out to be wrong. The more we understand the discipline, the better our
intuition becomes.
At this stage in history, it would be very presumptuous to claim that we have good
intuition about the
nature of efficient computation
. In particular, we do not even know
the answers to such basic questions as whether or not
,
let alone have an understanding of what makes one computational problem hard while
a seemingly related problem is easy. Consequently, we should be extremely careful
when making assertions about what can or cannot be efficiently computed. Unfortu-
nately,
making assertions about what can or cannot be efficiently computed is exactly
what cryptography is all about
. Worse yet, many of the problems of cryptography
have much more complex and cumbersome descriptions than are usually encountered
in complexity theory. To summarize, cryptography deals with very complex computa-
tional notions and currently must do so without having a good understanding of much
simpler computational notions. Hence, our current intuitions about cryptography must
be considered highly unsound until they can be formalized and examined carefully. In
other words, the general need to formalize and examine intuition becomes even more
acute in a highly sensitive field such as cryptography that is intimately concerned with
questions we hardly understand.
P
is strictly contained in
NP
The Track Record.
Cryptography, as a discipline, is well motivated. Consequently,
cryptographic issues are being discussed by many researchers, engineers, and layper-
sons. Unfortunately, most such discussions are carried out without precise definitions
of the subject matter. Instead, it is implicitly assumed that the basic concepts of cryp-
tography (e.g., secure encryption) are self-evident (because they are so natural) and
that there is no need to present adequate definitions. The fallacy of that assumption is
demonstrated by the abandon of papers (not to mention private discussions) that derive
and/or jump to wrong conclusions concerning security. In most cases these wrong con-
clusions can be traced back to implicit misconceptions regarding security that could not
have escaped the eyes of the authors if they had been made explicit. We avoid listing
all such cases here for several obvious reasons. Nevertheless, we shall mention one
well-known example.
Around 1979, Ron Rivest claimed that no signature scheme that was “proven secure
assuming the intractability of factoring” could resist a “chosen message attack.” His
argument was based on an implicit (and unjustified) assumption concerning the nature of
a “proof of security (which assumes the intractability of factoring).” Consequently, for
several years it was believed that one had to choose between having a signature scheme
“proven to be unforgeable under the intractability of factoring” and having a signature
scheme that could resist a “chosen message attack.” However, in 1984, Goldwasser,
Micali, and Rivest pointed out the fallacy on which Rivest's 1979 argument had been
based and furthermore presented signature schemes that could resist a “chosen message
attack,” under general assumptions. In particular, the intractability of factoring suffices
