Cryptography Reference
In-Depth Information
was replaced by certification by cryptanalytic assault. . . . Although some general
rules have been developed, which aid the designer in avoiding obvious weaknesses,
the ultimate test is an assault on the system by skilled cryptanalysts under the most
favorable conditions (e.g., a chosen plaintext attack). The development of computer
has led for the first time to a mathematical theory of algorithms which can begin
to approach the difficult problem of estimating the computational difficulty of
breaking a cryptographic system. The position of mathematical proof may thus
come full circle and be reestablished as the best method of certification.7
7
Yet the realization of this aspect of Diffie and Hellman's program has enc-
ountered surprisingly tenacious difficulties. The mathematical successes
flowing from the framing of cryptography within computational complex-
ity and algorithmics are undisputed. A broad range of number-theoretic
primitives (e.g., encryption, digital signatures, pseudorandom generators)
have been defined and analyzed by cryptographers working within the
computational complexity framework. These primitives have been further
assembled into protocols that enable parties communicating over networks
to realize remarkable communication feats
—
e.g., flip coins or exchange
cash anonymously
—
with the certainty of mathematical proof. However,
the practical payoffs have been less spectacular. The impact of provable
security on fielded cryptographic systems has been disappointingly small,
“in the sense that these ideas were reflected almost not at all in protocols
used in practice.”
8
Mihir Bellare and Philip Rogaway have suggested that the cryptographic
theory/practice divide is due to the fact that “theoretical work often seems
to gain provable security only at the cost of efficiency.”9
9
Block ciphers,
such as DES, have remained the most popular atomic primitive, as they
are much more efficient than number-theoretic primitives such as RSA
encryption. Indeed, “DES is generally at least 100 times as fast in software
and between 1,000 and 10,000 times as fast in hardware, depending on
the implementation.”
10
Yet the provable security line of work has relied
exclusively on number-theoretic primitives as the foundation for protocol
design because they are characterized by well-defined mathematical
problems.
The problem is compounded by the fact that, over the last thirty-five
years, very few new, possibly faster, number-theoretic problems have
emerged that have withstood the test of time: “Good atomic primitives are
rare, as are people who understand their workings . . . The reason is that
