Cryptography Reference
In-Depth Information
surrounding the epistemological implications of the “Random Oracle
Model.” Because the controversy has grown increasingly acrimonious
in recent years, I will tread very lightly, with the modest goal of arguing
two related points: first, that in contrast with the rest of the crypto-
graphic signature model, the controversy represents an engagement of the
cryptographic research community with the question of what constitute
acceptable abstractions in mathematical modeling; second, that the com-
munity pragmatically recognizes that “provable security” obtains under a
broad range of assumptions about the physical world.
6
The Random Oracle Model
Yet another dimension of the revolution prophesied by Diffie and Hellman
in “New Directions” concerned methods for certification of the soundness
of cryptographic systems. At the time, such certification came with a large
disclaimer: after surviving sustained cryptanalytic examination by the
community, a cryptosystem such as DES would be certified as “free of
weaknesses,
as far as the community is aware
.” The caveat underlined the
recognition that the research community could not guarantee that, on the
one hand, such cryptosystems would not fall in the future to yet undis-
covered attacks, and on the other hand, that such methods had not already
been discovered but undisclosed (e.g., by the intelligence establishment).
The only exception to the rule concerned the Vernam one-time pad,
proven absolutely secure under Shannon's information-theoretic frame-
work, at the cost of an equally absolute impracticality.
In “New Directions,” Diffie and Hellman claimed that two emerging
mathematical disciplines, computational complexity and algorithmics,
would offer an alternative. Less haphazard than conviction obtained
through practical experience and community consensus, more practical
than information theory,
provable security
would provide the surest method
of certification:
Judging the worth of new systems has always been a central concern of cryptogra-
phers. During the sixteenth and seventeenth centuries, mathematical arguments
were often invoked to argue the strength of cryptographic methods, usually relying
on counting methods which showed the astronomical number of possible keys. . . .
As systems whose strength had been so argued were repeatedly broken, the notion
of giving mathematical proofs for the security of systems fell into disrepute and
