{"id":2059,"date":"2014-11-16T09:41:29","date_gmt":"2014-11-16T14:41:29","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=2059"},"modified":"2017-01-13T06:59:59","modified_gmt":"2017-01-13T11:59:59","slug":"what-does-nsa-think-of-academic-cryptographers-recently-declassified-document-provides-clues","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=2059","title":{"rendered":"What does the NSA think of academic cryptographers?  Recently-declassified document provides clues"},"content":{"rendered":"<p><a href=\"http:\/\/web.engr.illinois.edu\/~pbg\/\">Brighten Godfrey<\/a> was one of my officemates when we were grad students\u00a0at Berkeley. \u00a0He&#8217;s now a highly-successful computer networking professor at the University of Illinois Urbana-Champaign, where he studies the wonderful\u00a0question of how\u00a0we could get the latency of the Internet down to the physical limit imposed by the finiteness\u00a0of the speed of light. \u00a0(Right now, we&#8217;re away from that limit\u00a0by a factor of about 50.)<\/p>\n<p>Last week, Brighten brought to my attention a remarkable document: a <a href=\"https:\/\/www.nsa.gov\/public_info\/_files\/cryptologs\/cryptolog_126.pdf\">1994 issue of CryptoLog<\/a>, an NSA internal newsletter, which was recently declassified with a few redactions. \u00a0The most interesting thing in the newsletter\u00a0is a trip report (pages 12-19 in the newsletter, 15-22 in the PDF file)\u00a0by an unnamed NSA cryptographer, who attended the 1992 EuroCrypt conference, and who details his opinions on\u00a0just about every talk. \u00a0If you&#8217;re interested in crypto, you really need to read this thing all the way through, but here&#8217;s a small sampling of the zingers:<\/p>\n<ul>\n<li>Three of the last four sessions were of no value\u00a0whatever, and indeed there was almost nothing at Eurocrypt\u00a0to interest us (this is good news!). The scholarship\u00a0was actually extremely good; it&#8217;s just that the directions\u00a0which external cryptologic researchers have taken are\u00a0remarkably far from our own lines of interest.<\/li>\n<li>There were no proposals of cryptosystems, no\u00a0novel cryptanalysis of old designs, even very little on\u00a0hardware design. I really don&#8217;t see how things could\u00a0have been any better for our purposes. We can hope that\u00a0the absentee cryptologists stayed away because they had\u00a0no new ideas, or even that they&#8217;ve taken an interest in\u00a0other areas of research.<\/li>\n<li>Alfredo DeSantis &#8230;\u00a0spoke on &#8220;Graph decompositions and secret-sharing\u00a0schemes,&#8221; a silly topic which brings joy to combinatorists\u00a0and yawns to everyone else.<\/li>\n<li>Perhaps it is beneficial\u00a0to be attacked, for you can easily augment your\u00a0publication list by offering a modification.<\/li>\n<li>This\u00a0result has no cryptanalytic application, but it serves to\u00a0answer a question which someone with nothing else to\u00a0think about might have asked.<\/li>\n<li>I think I have hammered home my point often\u00a0enough that I shall regard it as proved (by emphatic\u00a0enunciation): the tendency at IACR meetings is for academic\u00a0scientists (mathematicians, computer scientists,\u00a0engineers, and philosophers masquerading as theoretical\u00a0computer scientists) to present commendable research\u00a0papers (in their own areas) which might affect cryptology\u00a0at some future time or (more likely) in some other\u00a0world. Naturally this is not anathema to us.<\/li>\n<li>The next four sessions were given over to philosophical\u00a0matters. Complexity theorists are quite happy\u00a0to define concepts and then to discuss them even though\u00a0they have no examples of them.<\/li>\n<li>Don Beaver (Penn State), in another era, would\u00a0have been a spellbinding charismatic preacher; young,\u00a0dashing (he still wears a pony-tail), self-confident and\u00a0glib, he has captured from Silvio Micali the leadership\u00a0of the philosophic wing of the U.S. East Coast cryptanalytic\u00a0community.<\/li>\n<li>Those of you who know my prejudice against\u00a0the &#8220;zero-knowledge&#8221; wing of the philosophical camp\u00a0will be surprised to hear that I enjoyed the three talks of\u00a0the session better than any of that ilk that I had previously\u00a0endured. The reason is simple: I took along some\u00a0interesting reading material and ignored the speakers.\u00a0That technique served to advantage again for three more\u00a0snoozers, Thursday&#8217;s &#8220;digital signature and electronic\u00a0cash&#8221; session, but the final session, also on complexity\u00a0theory, provided some sensible listening.<\/li>\n<li>But it is refreshing to find a\u00a0complexity theory talk which actually addresses an\u00a0important problem!<\/li>\n<li>The other two talks again avoided anything of\u00a0substance. \u00a0[The authors of one paper]\u00a0thought it worthwhile,\u00a0in dealing [with] the general discrete logarithm problem,\u00a0to prove that the problem is contained in the\u00a0complexity classes NP and co-AM, but is unlikely to be\u00a0in co-NP.<\/li>\n<li>And Ueli Maurer, again dazzling us with his\u00a0brilliance, felt compelled, in &#8220;Factoring with an Oracle&#8221;\u00a0to arm himself with an Oracle (essentially an Omniscient\u00a0Being that complexity theorists like to turn to\u00a0when they can&#8217;t solve a problem) while factoring. He&#8217;s\u00a0calculating the time it would take him (and his Friend)\u00a0to factor, and would like also to demonstrate his independence\u00a0by consulting his Partner as seldom as possible.\u00a0The next time you find yourself similarly equipped,\u00a0you will perhaps want to refer to his paper.<\/li>\n<li>The conference again offered an interesting view\u00a0into the thought processes of the world&#8217;s leading &#8220;cryptologists.&#8221;\u00a0It is indeed remarkable how far the Agency\u00a0has strayed from the True Path.<\/li>\n<\/ul>\n<p>Of course, it would be wise not to read <em>too<\/em> much into this: it&#8217;s not some official NSA policy statement, but the griping of a single, opinionated individual somewhere within the NSA, who was probably\u00a0bored and trying\u00a0to amuse his colleagues. \u00a0All the same, it&#8217;s a fascinating document, not only for its zingers\u00a0about people who are still very much active on the cryptographic scene, but also for its candid insights into what the NSA cares about and why, and for its look into the subculture within cryptography that would lead, years later, to Neal Koblitz&#8217;s widely-discussed <a href=\"http:\/\/anotherlook.ca\/\">anti-provable-security manifestos<\/a>.<\/p>\n<p>Reading this document drove home for\u00a0me that the &#8220;provable security wars&#8221; are a very simple matter of the collision of two communities with different intellectual goals, not of one being right and the other being wrong.\u00a0 Here&#8217;s a\u00a0fun\u00a0exercise: try reading this trip report while remembering that, in the 1980s&#8212;i.e., the decade immediately preceding the maligned\u00a0EuroCrypt conference&#8212;the &#8220;philosophic wing&#8221; of cryptography that the writer lampoons\u00a0<em>actually succeeded<\/em> in introducing revolutionary concepts (interactive proofs, zero-knowledge, cryptographic pseudorandomness, etc.) that transformed\u00a0the field, concepts\u00a0that have now been\u00a0recognized with\u00a0no fewer\u00a0than\u00a0three Turing Awards (to Yao, Goldwasser, and Micali). \u00a0On the other hand, it&#8217;s undoubtedly true that this progress was of no immediate interest to the NSA. \u00a0On the third hand, the &#8220;philosophers&#8221; might reply that helping the NSA wasn&#8217;t their goal. \u00a0The best interests of the NSA don&#8217;t <em>necessarily<\/em>\u00a0coincide with the best interests of scientific advancement\u00a0(not to mention the best interests of humanity&#8212;but that&#8217;s a separate debate).<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Brighten Godfrey was one of my officemates when we were grad students\u00a0at Berkeley. \u00a0He&#8217;s now a highly-successful computer networking professor at the University of Illinois Urbana-Champaign, where he studies the wonderful\u00a0question of how\u00a0we could get the latency of the Internet down to the physical limit imposed by the finiteness\u00a0of the speed of light. \u00a0(Right now, [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"_wpas_customize_per_network":false,"jetpack_post_was_ever_published":false},"categories":[5,11],"tags":[],"class_list":["post-2059","post","type-post","status-publish","format-standard","hentry","category-complexity","category-nerd-interest"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/2059","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2059"}],"version-history":[{"count":5,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/2059\/revisions"}],"predecessor-version":[{"id":2064,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/2059\/revisions\/2064"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2059"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2059"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2059"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}