LETTER TO THE EDITOR OF THE NOTICES OF THE AMS [by Avi Wigderson]
=================================================================

I have read the article "The uneasy relationship between mathematics and
cryptography" by Neal Koblitz. A major part of the paper is a petulant
attack against the field of research he calls "provable
security", which I will call here by its standard name, Foundations of
Cryptography. The paper contains baseless charges which are defended by
imaginary, anecdotal or self-contradictory arguments.

In this short space I cannot argue the value of
rigorous proofs and asymptotic analysis for understanding practical
systems. I will only attempt to fix one flaw in Koblitz' paper, and
give a brief but accurate account of the history and impact of this field.

Like all areas in theoretical computer science, Foundations of Cryptography
is a mathematical discipline that studies computational notions.
Its main goal is to put on firm, rigorous
foundations such fundamental notions as *secret*, *privacy*, *knowledge*
and more. Being "complexity-based" it relates the
security of various protocols (for achieving diverse tasks, from secure
communication, to digital signatures, electronic cash, voting etc.) to
the difficulty of solving computational problems. A typical research
paper in this area proves mathematical theorems showing that the
security of a protocol (both terms fully specified) can be violated only
if an efficient algorithm to seemingly hard computational problem exist.
The huge value of such theorems is that understanding a highly
complex, counterintuitive scenario with several, adversarial parties,
reduces to a clean question about the difficulty of a single function.

In the 1980's, the first decade of the field, huge progress was made on
mathematically defining the subtle notions of cryptography. Moreover, it
revealed the power the assumptions underlying public-key encryption in
the breakthrough papers of Diffie-Hellman and Rivest-Shamir-Adleman,
which were shown to have a host of other diverse cryptographic
consequences. This mathematical study was performed
almost solely by theoretical computer scientists, driven mostly by good
old-fashioned mathematical curiosity, the depth and subtlety of the
millenia-old concepts involved, and the magical consequences of a world
in which difficult problems enable, rather than disable, progress.

This body of work laid the foundation for immense practical
applications of e-commerce once the Internet revolution arrived in the
90's. Its depth and beauty attracted top mathematicians, both to
find new math problems on which to base cryptosystems,
as well as attack such systems by finding better algorithms for such
problems. Finally, this body of work spun and
enriched new fields in theoretical computer science, including
pseudorandomness, interactive proofs and computational learning theory.

In the past 20 years, this field has interacted with its applied
side in the best way any area of applied math can. It incorporated new
technological
advances and restrictions into its models, further improved efficiency
of protocols, and reduced computational assumptions. Needless to say,
much more can and will be done. But perhaps
foundations of cryptography has been even closer to practice than
other fields. The reason is the adversarial, unexpected nature of
cryptographic scenarios which almost precludes testing and intuitive
grasp of protocols, thus creating a much stronger reliance on clear
models and theorems.

Nevertheless, the tension between the practical and theoretical exists
in cryptography as well as other applied areas,
due to the natural differences in motivation of commercial applications
and mathematical research. In all of them, one can bemoan the
deficiencies of a mathematical model or theorem for practical
application. Or instead, one can delight in the clarity, insight,
guidance and indeed, the *proofs* they
provide, for practical innovation and design. Take your pick! And best
of all, one should continue research, implementation and interaction,
instead of slander.