tag:blogger.com,1999:blog-3722233.post76932302332572637..comments2024-03-18T17:27:11.613-05:00Comments on Computational Complexity: The Koblitz Controversy: A reactionLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger60125tag:blogger.com,1999:blog-3722233.post-26837029603109177932010-10-20T05:38:47.090-05:002010-10-20T05:38:47.090-05:00I am still reading this paper. So, I am unable to ...I am still reading this paper. So, I am unable to suggest whether it contributes more heat or light to the subject matter. <br /><br />But, 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. <br /><br />"It is the mark of an educated mind to be able to entertain a thought without accepting it."<br />Aristotle (384 BC - 322 BC)<br /><br />I hope that there are enough "educated minds" in the field of cryptography.Kapali Viswanathanhttps://www.blogger.com/profile/10169071482874609304noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8257787383681615662009-08-26T02:52:53.960-05:002009-08-26T02:52:53.960-05:00Some weaknesses are identified in the (C,H)MQV pro...Some weaknesses are identified in the (C,H)MQV protocols, <br />see http://eprint.iacr.org/2009/408<br />for further details.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67452387298694488712008-01-15T14:51:00.000-06:002008-01-15T14:51:00.000-06:00I think a possible way to pick up PC for a confere...I 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-53805274763238032722008-01-15T14:37:00.000-06:002008-01-15T14:37:00.000-06:00Alfred and Neal criticized the minor contribution ...Alfred 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-42762097883483707382007-10-01T03:44:00.000-05:002007-10-01T03:44:00.000-05:00Several people asked me to post my ICALP paper on ...Several 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3205519330223498802007-09-18T21:47:00.000-05:002007-09-18T21:47:00.000-05:00Most people here seem to be miffed about the "leav...Most 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?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86499573812415419652007-09-17T15:51:00.000-05:002007-09-17T15:51:00.000-05:00One of the criticism in Koblitz's paper is that pe...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..... :-)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-21144080848581097462007-09-17T08:42:00.000-05:002007-09-17T08:42:00.000-05:00"This is not correct. Much of the research in prov..."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)."<BR/><BR/>Sorry, 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.<BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-84795193918551607952007-09-15T06:53:00.000-05:002007-09-15T06:53:00.000-05:00But are these points *actually* being addressed. P...<I>But are these points *actually* being addressed. People seem to pay them lip service, but not actually fix them. </I><BR/><BR/>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).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-50300638983086209792007-09-14T17:28:00.000-05:002007-09-14T17:28:00.000-05:00"Well, sure. I've heard those same criticisms from..."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."<BR/><BR/>But 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22039132106430982512007-09-12T11:43:00.000-05:002007-09-12T11:43:00.000-05:00An update: the Notices of the AMS has agreed to pu...An update: the Notices of the AMS has agreed to publish (a shortened version of) my letter.Jonathan Katzhttps://www.blogger.com/profile/07362776979218585818noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-43954723633399640822007-09-11T05:49:00.000-05:002007-09-11T05:49:00.000-05:00The term "provably secure" was probably chosen to ...<I>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.</I><BR/><BR/>I 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.<BR/><BR/>The two caveats of proofs of security are: <BR/><BR/>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.<BR/><BR/>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.<BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4558568223848189252007-09-09T09:47:00.000-05:002007-09-09T09:47:00.000-05:00Most researchers in theoretical CS (especially of ...<I> 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.</I><BR/><BR/>They 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-25149853601547080712007-09-07T12:05:00.000-05:002007-09-07T12:05:00.000-05:00Alfred Hoffman has pointed out to me that Ivan's p...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.Alvin Anonyhttps://www.blogger.com/profile/15268049341572923471noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47669537297226540452007-09-07T08:03:00.000-05:002007-09-07T08:03:00.000-05:00"any intelligent cryptographer"An oxymoron?regards..."any intelligent cryptographer"<BR/><BR/>An oxymoron?<BR/><BR/>regards<BR/><BR/>http://www.prosefights.org/nmlegal/mcconnell/pacer/Payne%20Tutors%20RSA%20and%20NSA.htm<BR/><BR/>http://www.prosefights.org/nmlegal/dcvoid/dcvoid.htm#feehan3<BR/><BR/>http://www.alineshat.com/PDF/Nojeh-LawSuit-Doc.pdfAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87847916437401833252007-09-07T04:06:00.000-05:002007-09-07T04:06:00.000-05:00The paper by Ivan Damgard is unfortunately unavail...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!)<BR/><BR/>I 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.<BR/><BR/>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.<BR/><BR/>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.<BR/><BR/>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.<BR/><BR/>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.<BR/><BR/>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:<BR/><I><BR/>Security does not exist in nature, nor do the children of men as a whole experience it. <BR/></I>Alvin Anonyhttps://www.blogger.com/profile/15268049341572923471noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90639492328779526312007-09-06T21:25:00.000-05:002007-09-06T21:25:00.000-05:00I think that the "marketing ploy" argument is way ...I think that the "marketing ploy" argument is way off base (not to mention rather insulting). <BR/><BR/>For 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.")<BR/><BR/>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.) <BR/><BR/>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 <A HREF="http://eprint.iacr.org/" REL="nofollow">Cryptology ePrint Archive</A>, and tried to extract what these 50 abstracts claimed about provable security. You can read the details on <A HREF="http://people.csail.mit.edu/shaih/provable.html" REL="nofollow">this page</A>, but the bottom line is that not a single one of these 50 abstracts can be called a "marketing ploy". <BR/><BR/>To me, this is a clear demonstration that the arguments about theoretical cryptographers over-hyping their provable-security results are essentially just mudslinging.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86118247132599378662007-09-06T07:17:00.000-05:002007-09-06T07:17:00.000-05:00I best liked Ivan Damgaard's reply to the original...I 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4264918505660447932007-09-06T07:12:00.000-05:002007-09-06T07:12:00.000-05:00Can anyone actually point to a specific example of...Can anyone actually point to a <EM>specific</EM> 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78610954311280062182007-09-06T04:11:00.000-05:002007-09-06T04:11:00.000-05:00I think that gap between crypto-English and normal...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"?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67198879367289289742007-09-05T23:02:00.000-05:002007-09-05T23:02:00.000-05:00Kevin (16), Koblitz'es latest paper is over the li...Kevin (16), Koblitz'es latest paper is over the line, not over the top. There is a difference there.<BR/><BR/>To 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. <BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19159513429721177962007-09-05T14:25:00.000-05:002007-09-05T14:25:00.000-05:00I postedherea letter that I submitted to the Edito...I posted<BR/><A HREF="http://www.ee.technion.ac.il/~hugo/ams-letter/" REL="nofollow">here</A><BR/>a letter that I submitted to the Editor of the Notices of the AMS in response<BR/>to the recent <BR/><A HREF="http://www.ams.org/notices/200708/tx070800972p.pdf" REL="nofollow">article</A><BR/>by Neal Koblitz in the Notices.<BR/>The letter is intended to tell, as concisely as I can, the REAL HMQV story,<BR/>and through it to tell the story of the amazing success of the Theory of<BR/>Cryptography (TOC). This success is reflected not only in the rigorous<BR/>mathematical foundations that TOC has laid for Cryptography at large, but also<BR/>in its ability to guide us in the design of truly practical solutions to<BR/>real-world problems. The HMQV design is a very good example of the latter<BR/>aspect of TOC, one that Koblitz tries to negate via personal attacks and<BR/>ridiculing of the whole field. There is no need to take my word on this,<BR/><A HREF="http://eprint.iacr.org/2005/176.pdf" REL="nofollow">the HMQV paper is available</A><BR/>for anyone to read, verify and judgeAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-77137746676611359662007-09-05T01:53:00.000-05:002007-09-05T01:53:00.000-05:00Nobody other than Perelman, the Fields committee, ...<I>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.</I><BR/><BR/>Maybe 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.<BR/><BR/><I>the Fields committee</I><BR/><BR/>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.)<BR/><BR/><I>Terence Tao</I><BR/><BR/>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).<BR/><BR/><I>Cao and Zhu themselves</I><BR/><BR/>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.<BR/><BR/><I>Nobody other than Perelman</I><BR/><BR/>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).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-53508369718239295242007-09-04T23:16:00.000-05:002007-09-04T23:16:00.000-05:00Nobody thinks Perelman wrote down his proof in any...<I>Nobody thinks Perelman wrote down his proof in anything like a reasonable form.</I><BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82700213486610989682007-09-03T21:27:00.000-05:002007-09-03T21:27:00.000-05:00Thank you very much for Comments 33-35. It's good...Thank you very much for Comments 33-35. It's good to see high-road non-snarky things that are also educational.Anonymousnoreply@blogger.com