(Guest Blog by Jonathan Katz on the Koblitz Controversy)
Like many
others, I was very upset by a recent
article by Neal Koblitz that appears in the Notices of the AMS.
I'll
say at the outset that I actually think the earlier papers by Koblitz (and
Menezes) contained some valid points --- I don't agree with their
conclusions,
and I find their tone objectionable, but I still think they raise some
issues
worthy of further thought.
What really bugs me, however, is how much publicity Koblitz has
managed to get
out of this. I see him invited to give talks at many venues,
but never see
anyone invited to present a counter-argument. (For that matter, I don't
see
invited speakers at cryptography conferences poking fun at the
cryptographic work that mathematicians do.)
This does not matter so much when Koblitz speaks
at a TCS-venue (any intelligent cryptographer
knows that his arguments are
overblown), but I think it matters greatly when he speaks in front of an
"outside"
audience.
For this reason, I thought publication of his article in the Notices of
the AMS was inexcusable. Even worse, this latest incarnation of his
essay goes beyond being a mere "academic" argument and degenerates to
name-calling and belittlement of an entire field
and all the people who work in it. (And
it seems pretty clear that his feelings extend beyond crypto to CS at
large.)
As
promised, I have written a letter of complaint to the editors of the
Notices. I don't know if it will get published (it is also a bit long),
but it is available
here (pdf)
or
here (ps)
P.S. After sending this post to Bill I noticed that Oded also
wrote
a letter
to the Notices of the AMS.
Regardless of the merits of his work in cryptography, Koblitz's criticisms of how theoretical computer science works are all too valid unfortunately, as most who are so critical of his article know and often acknowledge privately. It would be better for everyone if instead of shutting our minds to these criticisms and venting, we figure out the best way to bring theoretical computer science practices up to the standards expected of a mature mathematical discipline.
ReplyDeleteThe minute TCS becomes the mature mathematical discipline that you are dreaming of, I am out of the game.
ReplyDeleteThe TCS community seems to think it is very important to point out Koblitz exaggeration and hyperbole.
ReplyDeleteBut no one address his very valid criticism: the culture of cranking out inconsequential incremental papers.
1. My conjecture: all scientific areas do have the "incremental results" problem.
ReplyDeleteDoes any one have any data supporting the hypothesis that CS (or TCS) has a higher percentage of "incremental results" published in respectable journals/conferences?
If not, Koblitz' criticism is only as valid as "there are few women in CS," which though correct is hardly CS' own problem.
2. As someone pointed out in a comment from My Biased Coin blog, is "incremental results" such a bad thing for the advancement of science that one has to "criticize" in the manner that Koblitz did? As far as I can tell, the great Euler published quite a few "incremental results."
I think Koblitz's main criticism is not about "incremental results" --
ReplyDeletebut rather the practice of publishing hurriedly written, deadline bound, papers in poorly (some would say hardly) refereed conference proceedings, rather than in journals or
properly refereed proceedings as most mathematicians so. Add to this the deplorable practice of not caring to send conference papers to refereed journals and very soon "results" in theoretical CS by theoretical CS people would be treated rather circumspectly by the mathematical community (and trust me its not just Koblitz who hold this view).
Kobltiz's article just reads like a bunch of rants from a mathematician past his prime (which he is).
ReplyDeleteKoblitz's main criticism is ... the practice of publishing hurriedly written, deadline bound, papers in poorly (some would say hardly) refereed conference proceedings, rather than in journals or
ReplyDeleteproperly refereed proceedings as most mathematicians so.
In an earlier, equally out of place piece for one of those massive retrospective/prospective volumes on Mathematics at the end of the 20th century Koblitz complained bitterly about Crypto authors submitting exactly the same papers to a journal that had already been published in a conference proceedings. What this appears to be is a fundamental and deliberate misunderstanding of the legitimate CS theory approach to publication, namely that conference papers should not be counted on being more than extended abstracts and that true vetting for correctness is the reason for the separate journal publication.
We do have some outstanding conference papers that never made it to the second stage, e.g. Cook's original NP-completeness paper, which, together with the fact that our major conferences are more selective than our journals, causes people to place greater stock in conference papers than maybe they should but that is not a fundamental flaw in the process. The fast publication cycle of the CS theory conferences has been a major boon to innovation in the field, something that the 100's of math journals together cannot come close to emulating.
Koblitz longs for a simpler time when the pace of math was a lot slower and and math was not so corrupted by money and relevance. It is disappointing that these curmudgeonly tendencies are expressed in nasty ad hominem attacks.
It is disappointing that these curmudgeonly tendencies are expressed in nasty ad hominem attacks.
ReplyDeleteI disagree. I think Koblitz's article is fair, amusing, and has solid arguments. And moreover, his "Ad Hominem" attack seems more than justified in this case.
Actually, mathematics does have a "fast publication cycle" alternative -- which is to put papers on the arXiv. This works very well in practice, and in fact a morning ritual of most research mathematicians is to browse the arXiv mailing form the night before in his/her area. After a few months in the arXiv, hopefully generating some useful comments and criticisms, the paper would finally be submitted to a journal. There is no reason why such an approach could not be emulated in theoretical CS. Note that arXiv submissions are time-stamped -- a fact which might be critically important for our
ReplyDeleteyoung fast moving gen-X (or is it Y) theoretical CS researchers,
though perhaps not all that important for the staid, oldies
in mathematics (around for 3000 yrs as Koblitz points out).
Mathematicians also hold conferences, but presenting their work before a live audience and research interaction is the main motivation -- not publishing an "extended abstract". The proceedings of mathematics conferences if any are also subject to rather rigorous (perhaps a shade less than those of mathematics journals but incomparably more than
CS conferences) refereeing.
Anonymous #9: I like the arxiv for many reasons, but "useful comments and criticisms" is not one of them. Conferences work much better in this respect.
ReplyDeleteThough Alfred Menezes isn't a co-author with Koblitz on the AMS article, it's clear (based on past articles) that they are in cahoots.
ReplyDeleteIf he has such problems with the crypto community, why did he choose to chair the CRYTPO conference?
Koblitz is a liar
ReplyDeleteDo all those that think that there is some (or even lots) of merit in what Koblitz wrote, do not believe a word he says. Check the facts yourself. For instance, is Krawczyk's paper on HMQV on eprint halfbaked? See http://eprint.iacr.org/2005/176
The truth of course is that Koblitz and his NSA buddies published a half-baked protocol and managed to extract a lot of money from the US tax payers. He then accusses those who work hard and define, prove properties and refine the protocol of shoddy work. Amazing!
LT's swift boat analgy is perfect!
Koblitz is a liar....
ReplyDeleteI don't care what Koblitz is. I consider his general arguments and claims. And I agree with his opinion against CS publishing methods.
To 13, the critique of publishing habits in CS (note CS rather than TCS) is hardly the main point of the Koblitz article. It is just an add-on to get people's attention. To take such an article that
ReplyDelete(i) Claims that rigor is not needed in cryptography and can only hurt the design process.
(ii) Makes unjustified personal attacks against people who have dared to perform serious investigation into his own work and show its weakness.
and say "ohe, I don't about these things, I care about publishing in CS" is reckless behavior.
Agree with 14. Many of the responses here are pointing out that Koblitz has some reasonable criticisms of CS publishing habits. Well, sure. I've heard those same criticisms from plenty of active CS researchers, and agree with some of them myself. These points need to be addressed, fine. That's not why people are upset about Koblitz's article.
ReplyDeleteThe problem with the article was that 1. it repeatedly made some very insulting/inaccurate generalizations about CS research, 2. it for some reason argues that formal definitions and rigorous proofs are a bad thing (a position I think Koblitz only finds tenable because he already considers crypto and CS to be mathematical second-class citizens, the sort of snobbery that can say "Leave the proofs to us mathematicians, you'll only do it wrong, you just go with whatever seems to work"), and 3. he takes advantage of an AMS publication to gossip about a fellow researcher because of an apparent personal vendetta. This would all be one thing if Koblitz was publishing on a blog (No offense, Bill :) ), but in an AMS publication that will be seen and believed by a substantial portion of the mathematical community (at least in the US), this is inappropriate. His article may provide many mathematicians' first or only exposure to cryptography, and instead of helping to bridge the gap betwen crypto and mainstream math he fosters rivalries and makes false claims that could further alienate them from each other. This is a Bad Thing, and the fact that within all of this there are also some legitimate observations (that anyway would be more properly addressed within the CS/crypto community in the first place) does not justify the rest.
It would be easy for a knowledgeable member of the crypto community to write a point-by-point rebuttal to Koblitz, but many of the people most negatively affected by this would never see it. The damage has been done, and an entire mathematical community has essentially been slandered with no effective means of answering. That is why people are upset, not because we're over-defensive about our conference publishing habits.
I think part of the problem is that the theoretical CS community takes their models way too seriously and repeatedly claims to have defined security and proved that they achieved it. The complexity theoretic approach is extremely interesting science, but is a tiny piece of the puzzle for information security. For example it says nothing about what have come to be called side channel attacks. We'd all like to have a provably secure system, but it should start with a better definition of an adversary.
ReplyDeleteBy contrast the mathematicians have spent more time on what they see as interesting constructions (e.g., ECC), but have been reluctant to oversell the security of their constructions.
I was personally impressed with the discussion in the papers by Koblitz and Menezes, and not at all surprised by the reaction. Neal's latest paper is a bit over the top, but probably prompted by Oded's response (which was also over the top). Personally I think that Oded completely missed the point about the controversy. The problem is not that we should disdain proving things - it's that we should be much more careful in overselling that models of security reflect reality.
Personally I think that Oded completely missed the point about the controversy.
ReplyDeleteI agree that Koblitz has a good point about models: naive users will assume that a "provably secure" cryptosystem is provably secure in the real world, and they may not realize that the model could have serious weaknesses.
On the other hand, it's been many years since any cryptographic researchers made this mistake, so it's no wonder everyone's mad at Koblitz. Whatever valid criticisms he has are already well understood in the research community (even though we don't yet have perfect models). For example, everyone acknowledges that side channel attacks are very important and simply aren't addressed at all by Goldreich-style foundational work.
Koblitz's problem is that he loves to stand up for the little guy and combat whoever he sees as being in power. He's done this for decades in politics and education, but not so much in scientific research. Now he seems to be heading in that direction, but not in a sensibly thought out way.
david says:
ReplyDelete.... the sort of snobbery that can say "Leave the proofs to us mathematicians, you'll only do it wrong, you just go with whatever seems to work") ...
Harsh as it might sound, but there is some
merit to this argument. Most researchers in theoretical CS (especially of the younger generation) hardly take serious graduate level classes in mathematics, and hence have very little experience writing mathematical proofs. The proofs they produce, even when correct, are often not written in an optmial way, using non-standard terminology etc., reflecting lack of training. They are much better (compared to mathematicians) in developing new models, keeping up with technological advances and developing new solutions. Thus, a division of labor as suggested above might not be that bad an idea.
Anon 18, yeah, as opposed to the topologists...
ReplyDeleteanon 18 ---
ReplyDeletecould you mention a few STOC/FOCS/SODA/CCC/CRYPTO papers that illustrate this shabby untrained writing style?
(ii) [Koblitz] Makes unjustified personal attacks against people who have dared to perform serious investigation into his own work and show its weakness.
ReplyDeleteI can't see where Koblitz makes such unjustified attacks.
On the other hand, Goldreich is the one who makes personal/ideological attacks in his paper "On Post-Modern Cryptography".
E.g, look at one of the opening lines:
In our opinion at the last
account both post modernism and the critique of rigorous analysis in Modern Cryptography are reactionary , i.e., they play to the hands of the opponents of progress.
This line is out of place and overly aggressive. It is also probably based on the author's subjective political beliefs, which are quite unrelated.
If there is a problem with the training of TCS/crypto students in the ability to write good proofs then what ought to be addressed is ways of improving it. The answer is not just giving up and leaving proofs to mathematicians.
ReplyDeleteIt seems somewhat incorrect to say tha mistakes are happening in crypto proofs more often than we would like. The problem is actually seems that sometimes claims/proofs aren't as formal as one would like. Of course, this gives the opposite of Koblitz's conclusion: it is not about going more on intuition but beefing up on rigor.
It seems like some of the confusion here stems from historical inaccuracy. In particular Koblitz and Menezes in their earlier article use the OAEP CCA security "proof" as a main example of how proofs can be flawed, but actually what happened in this case was that there was *no* proof of CCA security (the scheme was [correctly] proven to meet a different security notion that was claimed to imply CCA), nor even was CCA even defined in that paper. Again, the point is that it may not be an issue of cryptographers not being able to "do proofs" in general but of using better formalizations and proof methodologies. It does seem like steps are being taken nowadays to address this.
anon21, in saying the attack was unjustified I wasn't saying that Goldreich was completely in the right in that situation, but that Notices of the AMS was not an appropriate place to call him to task. If Koblitz wanted to pursue that controversy through snarky letters and editorials within the crypto community, I would find that distasteful, but to take advantage of a Notices article to air that kind of gossip to the mathematical community as a whole is highly inappropriate and unjustified.
ReplyDeleteLike I said, most of people's angry reactions to this article can't be addressed by listing areas where he might have had a point, because for one thing there are only pieces of the article where that's true, and for another thing even where he did have a point, that was not the place to make it.
Kevin (#16), I think your criticisms are off-base. The theoretical CS community "takes their models seriously" because they are the best models we have. But no one claims that something secure in these models is guaranteed to be secure in the real world. (How can they? There can always be an implementation error, at a minimum...)
ReplyDeleteStill, a scheme with a proof (even in an imperfect model) is better than one without a proof. Both schemes may be vulnerable to side channel attacks (the modeling of which is an active area of research, by the way), but at least the first will not be vulnerable to a more direct attack.
I also wrote a letter to the editor (I posted a copy on Luca's blog). Just some clarifications:
ReplyDelete1. There is a healthy debate within the crypto community about the relative importance of proofs vs. practicality. However this is in the case where there is an alternative of an efficient protocol without analysis and an inefficient protocol with analysis. Koblitz argues that even when the protocols have the same efficiency (such as the HMQV and MQV protocols, where the HMQV is either as efficient or more efficient than MQV depending on setting of parameters), one should go for the protocol without analysis.
2. Furthermore, and this I find even more troubling, in this and the earlier essays Koblitz seems to argue even against formal definitions of security. These formal definitions are what allows for progress with people building on other people's work by refining the definitions, finding proofs or counterexamples, etc.. Without this crypto would just be a collection schemes (and insecure ones at that, since there is no one scheme that was perfect when suggested and did not benefit from a process of refinement guided by definitions).
3. There are arguments for and against conference vs. journal publications, but I didn't see any such argument in Koblitz's paper. I agree that there are not enough journal publications and full proofs in CRYPTO. (BTW the situation is much better in FOCS/STOC where often a full version is already prepared at the time of submission with the full proofs attached as appendics; perhaps it has to do with the fact that FOCS/STOC have non-anonymous submissions.)
4. Personally I find CS papers generally better written than Math papers, with more explanations and intuitions. But of course it far more depends on the author - there are computer scientists that are horrible writers and mathematicians who write beautifully.
5. Complaining about the level of writing, correctness of proofs, and "majorness" of the problems solved is like complaining about the whether. We'd all like all papers to be beautifully written, without any errors, and solve major problems; that's always true in any field. However, Koblitz's disparagement of computer scientists as writing "many worthless papers" reminds me of the saying "there are no small parts only small actors". Science is built not just by the major results that (justifiably) get a lot of attention but also by a lot of incremental progress, without which the major results could not get done.
Boaz Barak
anon 22 says: " ... It seems somewhat incorrect to say tha mistakes are happening in crypto proofs more often than we would like. The problem is actually seems that sometimes claims/proofs aren't as formal as one would like."
ReplyDeleteI would like to point out, that apart from the issue of whether one can trust an electronic computer, there is absolutely no debate amongst mathematicians about what constitutes a proof. There is no such thing as "informal claims/proofs" in mathematics -- and if this is what Crypto/TCS people are producing, then indeed Koblitz has a point.
Anon 11:51 am "there is absolutely no debate amongst mathematicians about what constitutes a proof"
ReplyDeletei find this claim odd in light of the recent perelman-yau-* controversy.
-Ranjit.
There is no such thing as "informal claims/proofs" in mathematics -- and if this is what Crypto/TCS people are producing, then indeed Koblitz has a point.
ReplyDeleteWell, they don't, and he doesn't.
ReplyDelete"there is absolutely no debate amongst mathematicians about what constitutes a proof"
i find this claim odd in light of the recent perelman-yau-* controversy.
The Perelman-Yau and many other such controversies in mathematics are about the authorship of proofs, not about correctness of the proofs.
Of course, it is ludicrous to compare such deep and difficult proofs of mathematics, with Crypto/TCS related results. Here the issue is mostly whether the objects and statements are precisely defined in the mathematical sense -- the proofs are certainly much less complex . This issue of mathematical formalism is of course irrelevant in the case of classical mathematical problems where such things have been worked out over centuries.
If the mathematical community has even a non-trivial fraction of people like Koblitz (and Yau), I now see the reason why people like Perelman quit the field. Koblitz has done damage to more than just the crypto community. He's hurt the mathematics community too. If fewer mathematicians work in crypto as a result of his article, Math has just lost a wonderful "application area".
ReplyDeleteOf course, it is ludicrous to compare such deep and difficult proofs of mathematics, with Crypto/TCS related results.
ReplyDeleteStraw man arguments are cheap.
Koblitz is indeed a reactionary. He wants a small group (him, the NSA) to determine what is secure without explicit criteria. The "theoreticians" give criteria and proofs. The proofs are not informal, just the opposite. If anything, when talking about concrete schemes the proofs are so detailed as to make them boring, which is a significant problem.
ReplyDeleteThe suggestion that there is no debate in mathematics about what constitutes a proof is not right.
ReplyDelete* As has been pointed out, the question of priority in the Perelman-Yau controversy was precisely about this. To what extent was what Perelman posted a full proof and to what extent did it need to be completed by Cao and Zhu or others. Things finally have been settled in this case for various political reasons. Since nobody is writing fully rigorous arguments it is clear that the notion of what is considered a complete proof is a social construct.
* The classification of finite simple groups was originally viewed as complete back in 1983 but there were gaps that took over a decade to fill and the entire proof is tens of thousands of pages, which likely contain errors. People are working on multiple revisions of the whole argument but there are hundreds of papers that rely on this classification.
* To what extent should one accept a proof that follows exhaustive search of cases by computer, such as that of the four color theorem? Its broad acceptance took more than a decade.
Virtually all written proofs are expressed at a high level and require some level of translation by the reader. The TCS standard is that the authors of a paper should provide additional intuition to help the reader with that translation. This is not usually the standard in Math. Personally, I find the inclusion of such intuition an essential aspect of good paper writing.
However, though there are big advantages for readability in having intuition explicitly stated, it can lead one astray. This can be particularly problematic when the subject is computational agents which provide much more complex behavior than is required for case analyses such as in the simple groups or graph coloring examples. I would guess that the major source of bugs in published conference papers is that the written intuition and formal details don't match.
I fully agree with the opinions aired by Paul Beame.
ReplyDeleteLet me put forward another example witnessing a lack of agreement between some members of the mathematical community about what constitutes a proof.
As long ago as 1993, Wu-Hi Hsiang published a long paper entitled "On the sphere packing problem and the proof of Kepler's conjecture", Internat. J. Math. 4 (1993), no. 5, 739--831. My understanding is that he firmly believed to have settled Kepler's conjecture, and that he did not like to see his proof criticized.
In his MathSciNet review for that paper Gábor Fejes Toth wrote:
"I think there is hope that Hsiang's strategy will work: at least the main inequalities seem to hold. As far as details are concerned, my opinion is that many of the key statements have no acceptable proofs. Typically, we are given arguments such as "the most critical case is...." followed by a statement that "the same method will imply the general case". The problem with arguments of this kind is not only that they require the reader to redo some pages of calculations, but, notoriously, that they occur at places where we expect difficulties and most frequently it is impossible to see how the same method works in the general case.
Hsiang might consider this objection "a dispute about subjective standards of how much detail a properly written mathematical proof has to contain" \ref[B. Cipra, Science 259 (1993), no. 5097, 894--895]. It is true that in cases when referees and editors fail to exercise their control, it is solely the author's responsibility to decide what is the appropriate amount of detail. However, he has to bear in mind that a mathematical proof is a social process: It is only the acceptance by the mathematical community which affirms the legitimacy of a proof.
If I am asked whether the paper fulfills what it promises in its title, namely a proof of Kepler's conjecture, my answer is: no. I hope that Hsiang will fill in the details, but I feel that the greater part of the work has yet to be done."
(The emphasis is mine.) Thomas Hales appears to have gone through all the steps of a proof of Kepler's conjecture, and his Flyspeck project aims at producing a formal proof of Kepler's conjecture, where formal proof is understood in the sense of the QED manifesto.
Virtually all written proofs
ReplyDeleteare expressed at a high level and require some level of translation by the reader. The TCS standard is that the authors of a paper should provide additional intuition to help the reader with that translation. This is not usually the standard in Math. Personally, I find the inclusion of such intuition an essential aspect of good paper writing.
Of course such intuition is a good idea, but it is not true that this is a characteristic trait of TCS. All fields involving proofs do this. This may be more or less visible to outsiders, depending on the material and on the author.
Personally I find CS papers generally better written than Math papers, with more explanations and intuitions.
Everyone finds the papers in his/her field better written and easier to read than those in any other area. I've heard countless people complain about the strange writing style of people in other fields, and how they inexplicably leave out important details (which are apparently common knowledge in that field) while emphasizing issues not of interest to the complainer. I've never heard anyone say the opposite.
As has been pointed out, the question of priority in the Perelman-Yau controversy was precisely about this. To what extent was what Perelman posted a full proof and to what extent did it need to be completed by Cao and Zhu or others.
Not at all. Everyone involved agreed that what Perelman posted contained a lot of brilliant ideas while many important details were missing. The proof was completed by Cao and Zhu and by Morgan and Tian. The dispute was about how much credit to award for filling in the missing details. This was also influenced by the fact that Perelman was completing an ambitious program begun by Hamilton (Yau's protege).
In other words, this dispute was about how to divide up the intellectual credit, not what constitutes a complete proof or an acceptably written paper. Nobody thinks Perelman wrote down his proof in anything like a reasonable form.
Let me put forward another example witnessing a lack of agreement between some members of the mathematical community about what constitutes a proof.
As long ago as 1993, Wu-Hi Hsiang published a long paper entitled "On the sphere packing problem and the proof of Kepler's conjecture", Internat. J. Math. 4 (1993), no. 5, 739--831. My understanding is that he firmly believed to have settled Kepler's conjecture, and that he did not like to see his proof criticized.
As far as I can tell, the only person on Hsiang's side of this dispute is Hsiang himself (and he was an editor of the journal that published his paper, which is itself somewhat scandalous).
Thank you very much for Comments 33-35. It's good to see high-road non-snarky things that are also educational.
ReplyDeleteNobody thinks Perelman wrote down his proof in anything like a reasonable form.
ReplyDeleteNobody other than Perelman, the Fields committee, Terence Tao, etc. Cao and Zhu themselves renamed their paper from "A Complete Proof..." to "Hamilton-Perelman's Proof..." in response to the controversy. You have not described this situation accurately.
Nobody other than Perelman, the Fields committee, Terence Tao, etc. Cao and Zhu themselves renamed their paper from "A Complete Proof..." to "Hamilton-Perelman's Proof..." in response to the controversy. You have not described this situation accurately.
ReplyDeleteMaybe I wasn't clear. The consensus is that Perelman had all the ideas in his head, and that his paper documents the most important and brilliant ideas required for the proof. Therefore he deserves the lion's share of the credit (with Hamilton also playing an important role through his previous work, and with Cao-Zhu and Morgan-Tian getting some credit for actually sorting out the details and writing them up, which is very much not an easy task). However, he did not write it down in anything like a reasonable form. A lot of people are offended that he supplied so few details. If he had submitted his papers to a journal, the referee's reports would have been scathing.
the Fields committee
The Fields medal committee offered Perelman a medal for making a brilliant contribution, even though it was insufficiently documented. If Cao-Zhu and especially Morgan-Tian had not fully verified the details, then he would not have been offered the medal. (In fact, the Morgan-Tian manuscript was intended to be announced at the ICM as part of the justification for the Fields medal, but the process was sped up after Cao and Zhu published their paper.)
Terence Tao
I'm not sure what Terry Tao has to do with this. He was not involved in checking Perelman's proof, I very much doubt he has read either of the complete accounts, and I don't recall his offering any public opinion on the matter (although I may be wrong).
Cao and Zhu themselves
Cao and Zhu renamed their paper to keep from looking like they were trying to steal the intellectual credit for the result, not because they suddenly realized that Perelman's write-up was acceptably detailed after all.
Nobody other than Perelman
I doubt even Perelman considers his arXiv papers to be a reasonable write-up. Most likely, he just wrote up as much as he had the patience for and then figured he would let the rest of the world sort it out. In any case, whatever Perelman thinks, the rest of the world is very dissatisfied with the papers (even though the ideas in them are amazing).
I posted
ReplyDeletehere
a letter that I submitted to the Editor of the Notices of the AMS in response
to the recent
article
by Neal Koblitz in the Notices.
The letter is intended to tell, as concisely as I can, the REAL HMQV story,
and through it to tell the story of the amazing success of the Theory of
Cryptography (TOC). This success is reflected not only in the rigorous
mathematical foundations that TOC has laid for Cryptography at large, but also
in its ability to guide us in the design of truly practical solutions to
real-world problems. The HMQV design is a very good example of the latter
aspect of TOC, one that Koblitz tries to negate via personal attacks and
ridiculing of the whole field. There is no need to take my word on this,
the HMQV paper is available
for anyone to read, verify and judge
Kevin (16), Koblitz'es latest paper is over the line, not over the top. There is a difference there.
ReplyDeleteTo your point, I disagree that "theoretical CS community takes their models way too seriously". As with any community, theoretical crypto has its own language, and "provable security" is an often-used token in that language.
True, this term does not mean exactly the same in the crypto literature as it does in everyday English. This point was made many times before (and will no doubt be made many times in the future). But it is not the theoretical cryptographers who "take their model too seriously"; in fact criticizing and extending the models are one of the most active areas of research in theoretical cryptography.
I think that gap between crypto-English and normal-English is regularly exploited as marketing ploy (perhaps more at the funding level than product). In the same way, if in a certain community "cancer curing" were widely understood to mean "contains vitamin C", wouldn't you have a problem with sales of "cancer curing elixir"?
ReplyDeleteCan anyone actually point to a specific example of where the term "provably-secure" was "exploited as marketing ploy" by academic cryptographers? (I'm not referring to marketing a paper here, but marketing a money-making product.) The people I have seen hawking provable security in products for sale have all been selling snake oil (or the one time pad) and are not cryptographers.
ReplyDeleteI best liked Ivan Damgaard's reply to the original Koblitz-Menezes paper, which he presented at ICALP 2007 (A "Proof-Reading" of some Issues in Cryptography). Online at http://www.springerlink.com/content/7252778202hl3086/fulltext.pdf (DOI: 10.1007/978-3-540-73420-8_2). Whereas others replied perhaps too emotionally, he calmly points out the deficiencies in the Koblitz-Menezes reasoning and the dangers behind adopting their approach.
ReplyDeleteI think that the "marketing ploy" argument is way off base (not to mention rather insulting).
ReplyDeleteFor one thing, the difference between everyday use of "provable secure" and its use in the crypto literature is not that big. To be specific, the difference is that (presumably) laymen interpret provable-security as an absolute thing, while in reality both the "provable" and the "security" have qualifiers: "provable" because most of our proofs are relative to unproven conjectures, and "security" because we prove things in well-defined mathematical models that are inherently different than the "real word" where these schemes will be deployed. (Quoting from Krawczyk's HMQV paper, "proofs are never stronger than the model and assumptions they are based on.")
Most theoretical cryptography papers are quite honest about this point. Many of them even include a separate discussion where the authors explain their interpretation of the proofs. (Two examples that are relevant to the current argument are Krawczyk's HMQV paper and the "revisiting the random-oracle" paper by Canetti, Goldreich and myself.)
Lest I'll be suspected in making straw-man arguments based a few papers that are very different than the norm, I decided to test the allegation that theoretical papers over-hype the aspects of provable security: I looked at the abstracts of the last 50 papers that contain the word "provable" and were posted to the Cryptology ePrint Archive, and tried to extract what these 50 abstracts claimed about provable security. You can read the details on this page, but the bottom line is that not a single one of these 50 abstracts can be called a "marketing ploy".
To me, this is a clear demonstration that the arguments about theoretical cryptographers over-hyping their provable-security results are essentially just mudslinging.
The paper by Ivan Damgard is unfortunately unavailable to anyone who has not paid the Springer tax on science. I wish I could read it (Shai - we need to fix the iacr access page for Springer!)
ReplyDeleteI am actually in agreement with the comment about the "gap between crypto-English and normal-English". The term "provably secure" was probably chosen to exploit the fact that "provably" and "incontrovertibly" are synonyms in English (at least Wordnet lists them as such). Non-specialists who look to the field for guidance in designing systems can easily be misled by such loaded language, whether it is intentional or not. After all it's not just secure, it's *provably* secure! Such hyperbole does a disservice to the science, and this is unfortunate.
I've heard several people in theoretical computer science disdain the use of "provably secure", and I think it would be wise to avoid it. The terminology "hypothetical security" or "theoretical security" is much more descriptive of the actual intent, but of course these don't carry the same marketing pizazz. If people are interested in doing science then this shouldn't matter. The complexity theory will be just as interesting.
Unfortunately there is considerably more heat than light being generated by Koblitz's latest paper and the reaction to it. I don't believe that people who practice the science of cryptography are guilty of misrepresentation, nor do I believe that the community practices anything but the highest standards of scientific integrity. The fact that an occasional bug in a proof is found is of little consequence, since that is true in every branch of mathematics.
Whether a result is incremental or not should also be left for history to judge. Adleman once told me that he initially regarded the RSA paper as an inconsequential contribution at the time.
When I said that people take their security models way too seriously, I meant that people sometimes forget that a model is not real life. I've even heard numerous times the statement that if P=NP, then cryptography isn't possible. This is simply gibberish. We could still have cryptography with polynomial separation between the capabilities of adversaries. Reductions would have to be treated more delicately, but cryptography and current trends in complexity theory are not equivalent concepts. One is a model of the other.
It's also possible that encryption is impossible under any reasonable model (at Eurocrypt last year I argued that this is probably true in the case of Internet communication). It's possible that Helen Keller was right:
Security does not exist in nature, nor do the children of men as a whole experience it.
"any intelligent cryptographer"
ReplyDeleteAn oxymoron?
regards
http://www.prosefights.org/nmlegal/mcconnell/pacer/Payne%20Tutors%20RSA%20and%20NSA.htm
http://www.prosefights.org/nmlegal/dcvoid/dcvoid.htm#feehan3
http://www.alineshat.com/PDF/Nojeh-LawSuit-Doc.pdf
Alfred Hoffman has pointed out to me that Ivan's paper is in ICALP, and is therefore not part of the IACR contract for access by members (that takes us off the hook Shai!). He thoughtfully sent me a copy anyway.
ReplyDeleteMost researchers in theoretical CS (especially of the younger generation) hardly take serious graduate level classes in mathematics, and hence have very little experience writing mathematical proofs.
ReplyDeleteThey might never register in GradMath 101, but they do take plenty of serious mathematics. The proofs covered in a grad course in complexity theory are as rigorous as those in any grad level course in math.
The term "provably secure" was probably chosen to exploit the fact that "provably" and "incontrovertibly" are synonyms in English (at least Wordnet lists them as such) ... The terminology "hypothetical security" or "theoretical security" is much more descriptive of the actual intent, but of course these don't carry the same marketing pizazz.
ReplyDeleteI don't know who coined it first, but I imagine that they chose it as the shortest term for denoting mathematical proofs of the security of protocols. I fail to see why "hypothetical security" or "theoretical security" are more descriptive.
The two caveats of proofs of security are:
1) computational assumptions being made; but often these are assumptions that are widely believed to be true (and so can be thought of as axioms) and in any case much stronger assumptions are implicitly made whenever using cryptography.
2) The fact that the proofs refer to a certain model and definition. This is inherent to doing cryptography, whether using proofs or not, there is no way for protocols, whether designed through proofs or intuition, to be secure irrespective of the way they are used.
As a two-word description, "provable security" is as good as any. The warning that even with provable security one needs to be careful on how the protocol is implemented is important, but it's not part of the two-word description (it should be in the abstract, not the title). Indeed, as Shai showed, almost always the claim "we show a provably-secure protocol" is followed with an explanation of what this means.
An update: the Notices of the AMS has agreed to publish (a shortened version of) my letter.
ReplyDelete"Well, sure. I've heard those same criticisms from plenty of active CS researchers, and agree with some of them myself. These points need to be addressed, fine. That's not why people are upset about Koblitz's article."
ReplyDeleteBut are these points *actually* being addressed. People seem to pay them lip service, but not actually fix them. Even if Koblitz is a self serving duplicitous jerk, it would be nice if there was real work to fix things.
But are these points *actually* being addressed. People seem to pay them lip service, but not actually fix them.
ReplyDeleteThis is not correct. Much of the research in provable security is exactly about coming up with more realistic definitions that encapsulate more realistic attacks (and of course coming up with constructions that meet these definitions).
"This is not correct. Much of the research in provable security is exactly about coming up with more realistic definitions that encapsulate more realistic attacks (and of course coming up with constructions that meet these definitions)."
ReplyDeleteSorry, I think I was unclear. One of Koblitz criticisms was that the current process is all about the rush to put stuff out, rather than to carefully vet results in a less time sensitive manner.
The question "What is the right model" does seem to be a question which the TCS community is very interested in. Koblitz complaints in that area seemed much more ridiculous.
One of the criticism in Koblitz's paper is that people rush to publish in cryptography. Well, his paper was not circulating around for people in the field to give comments about (before publication). Wasn't this publication a bit rushed, perhaps?.... (By self-reference argument, maybe this is Niel's way of claiming to be a cryptographer..... :-)
ReplyDeleteMost people here seem to be miffed about the "leave the proofs to the mathematicians" snobbery in Koblitz's article. However, I didnt get this impression at all. Where exactly does Koblitz say or allude to this?
ReplyDeleteSeveral people asked me to post my ICALP paper on my home page. This is now done. I'll resist the temptation of posting a long reply to many of the comments posted here. I think the paper says most of what I want say about this issue.
ReplyDeleteAlfred and Neal criticized the minor contribution from the major crypto conferences. I think it should be changed that several active cryptographers always stay in the PC. I am also unhappy that some papers with trivial contribution are accepted by quality conferences, probably because they are from active cryptographers. This thing happens (as I see now) to all the major conferences including TCC and CT-RSA. This year (2008), CT-RSA has one (as far as I know. I am not pointing to the PC chair since it is not clear how this occurs). This of course is unfair to other cryptographers. IACR should make some policy to prevent this. I think a possible way to include the PC members from people who even do not have many crypto papers. Note even they only have PKC level or even lower such as ACNS, ACISP et al, evaluating crypto papers is definitely of no problem.
ReplyDeleteI think a possible way to pick up PC for a conference is to put a call for PC of this conference at iacr. People who are willing to be one pc member can just simply registrate their name and homepage and the PC chair has the duty to finalize the members.
ReplyDeleteSome weaknesses are identified in the (C,H)MQV protocols,
ReplyDeletesee http://eprint.iacr.org/2009/408
for further details.
I am still reading this paper. So, I am unable to suggest whether it contributes more heat or light to the subject matter.
ReplyDeleteBut, I should say that I a bit surprised to witness the reactions from and gang-formations by mature scientists. The following wisdom comes to my mind when witnessing the reactions on this blog as well as outside it.
"It is the mark of an educated mind to be able to entertain a thought without accepting it."
Aristotle (384 BC - 322 BC)
I hope that there are enough "educated minds" in the field of cryptography.