Cryptography Reference
In-Depth Information
the design (or discovery) of good atomic primitives is more an art than a
science.”
11
Furthermore, cryptography deals with a problem significantly
different than the ordinary fare of computational complexity, that of defin-
ing secure protocols, that is, “distributed algorithms defined by a sequence
of steps precisely specifying the actions required of the two or more entities
to achieve a specific security objective.”
12
However, there has been no
straightforward path between good atomic primitives and good proto-
cols.
13
As Bellare points out, “the problem with protocol design is that a
poorly designed protocol can be insecure
even though the underlying atomic
primitive is good.
”
14
A significant component of the contemporary crypto-
graphic research program has thus sought to lay down well-defined prin-
ciples to guide designers in building provably secure, protocols, using
atomic primitives with precise mathematical properties.
Overall, this endeavor has failed to convince practitioners. As Phil
Rogaway recounts, cryptographic system designers have been “alienated
by the language of asymptotic complexity, the high level statements of
results that fell under it, and the algorithmic inefficiency that seemed
endemic to early work. There emerged a pronounced culture gap between
cryptographic theory and practice. Theorists and practitioners ignored one
another, attending disjoint conferences. Neither group regarded the other
as having anything much to say.”
15
One highly controversial proposal for restarting the conversation is
Bellare and Rogaway's program for “Practice-Oriented Provable Security,”
based on the Random Oracle Model (ROM). Bellare and Rogaway were
motivated by the persistent issues encountered in proving the security of
RSA signatures. As described in “The Early History” in chapter 4, RSA sig-
natures use a “hash-then-decrypt” approach: messages are first hashed and
then signed (“decrypted”) with the signer's private key. Proving the secu-
rity of RSA signatures thus requires taking into account the security proper-
ties of the hash function. But, as noted previously by Stinson, none of the
efficient hash functions used in practice (such as SHA-1 or MD5) are
founded on the kind number-theoretic problems that would enable their
analysis under the complexity theory framework. The security of RSA sig-
natures thus relies on a combination of computational assumptions and
on assumptions relative to the community's faith in the lack of known
attacks. Given the appeal of digital signatures as “non-repudiable” forensic
objects, this is an uncomfortable state of affairs. As Bellare and Rogaway
