mersenneforum.org > Math John Nash's letter to the NSA predecessors
 Register FAQ Search Today's Posts Mark Forums Read

 2012-02-19, 18:23 #1 Christenson     Dec 2010 Monticello 5·359 Posts John Nash's letter to the NSA predecessors All: This was recently declassified. I think it may be of general interest. http://agtb.wordpress.com/2012/02/17...er-to-the-nsa/ Christenson
 2012-02-19, 20:28 #2 ewmayer ∂2ω=0     Sep 2002 República de California 3·53·31 Posts Fascinating ... two comments: 1. "[Nash] is very well aware that this is a conjecture and that he cannot prove it. Surprisingly, for a mathematician, he does not even expect it to be solved. Even more surprisingly he seems quite comfortable designing his encryption system based on this unproven conjecture. This is quite eerily what modern cryptography does to this day: conjecture that some problem is computationally hard; not expect anyone to prove it; and yet base their cryptography on this unproven assumption." I wonder whether this might be another example of the same phenomenon that came up recently with respect to the alleged discovery of faster-than-light particles at CERN. I immediately offered to bet anyone $1000 that the alleged discovery would vanish under scrutiny, on "win-win" strategy that most of the time such 'finds" do prove spurious - in which case there is no exciting 'new physics' but I win some money - but in the remote probability that the find is real, that will be cool enough that I won't mind losing the money. In the present case, we believe "hard" problems really are hard, but we have no proof as yet. So for a mathematician who also enjoys gambling (game theory), if someone did manage to find a polynomial-time way to crack some believed-to-be-hard (and hence all, if we are speaking of "hard" in the formal NP-complete sense) problem like integer factorization, that would be such a once-in-a-lifetime amazing discovery, that the side effect of much of the world's digital-security infrastructure effectively vanishing would be a price worth paying. 2. Not being a crypto guy, I had not previously heard of Clifford Cocks having invented the "RSA" encryption algorithm in 1973, four years before R,S, and A first published it. Cocks’ work remained classified until 1997 - as does one of the article commenters, I wonder what if any the 'prior art' implications of that prior discovery-which-was-kept-secret might be. Also, once the algorithm was published in 1977 by the researchers whose initials it now bears, what would be the point of keeping Cocks' work classified? Is this just the usual paranoid-national-security apparatus M.O. of keeping as much stuff as possible classified for as long as possible, irrespective of the rationale for continued secrecy having vanished long ago? 2012-02-19, 20:48 #3 retina Undefined "The unspeakable one" Jun 2006 My evil lair 5×1,223 Posts Quote:  Originally Posted by ewmayer Also, once the algorithm was published in 1977 by the researchers whose initials it now bears, what would be the point of keeping Cocks' work classified? Is this just the usual paranoid-national-security apparatus M.O. of keeping as much stuff as possible classified for as long as possible, irrespective of the rationale for continued secrecy having vanished long ago? Yes, of course. No one wants to put their career on the line by actually making a decision. It is much easier to CYA and only release stuff when the laws say you have to.  2012-02-20, 03:08 #4 LaurV Romulan Interpreter Jun 2011 Thailand 249916 Posts That is really interesting material. Remember what I said somewhere here around, half year ago, quoting Fred Cohen (I love his books!): "we never approve" (for export, for use in software products, for making public, whatever) "something we can not decrypt". 2012-02-20, 07:29 #5 xilman Bamboozled! "𒉺𒌌𒇷𒆷𒀭" May 2003 Down not across 29×367 Posts Quote:  Originally Posted by ewmayer Also, once the algorithm was published in 1977 by the researchers whose initials it now bears, what would be the point of keeping Cocks' work classified? Is this just the usual paranoid-national-security apparatus M.O. of keeping as much stuff as possible classified for as long as possible, irrespective of the rationale for continued secrecy having vanished long ago? Never ascribe to malice that which is adequately explained by incompetence. Bureaucratic organizations, and especially intelligence organizations, usually move exceedingly slowly. 2012-02-20, 15:13 #6 Dubslow Basketry That Evening! "Bunslow the Bold" Jun 2011 40<A<43 -89<O<-88 3·29·83 Posts Quote:  Originally Posted by xilman Bureaucratic organizations, and especially intelligence organizations, usually move exceedingly slowly. Better safe than sorry. (Or rather, that's what I guess their typical reasoning is.)  2012-02-24, 04:23 #7 jasong "Jason Goatcher" Mar 2005 3·7·167 Posts Not to be a troll, but what sort of security could we have if we decided to only base things on proven assumptions? I honestly have no idea how this will be answered. If there are adequate ways to secure computers than we should use them, but if alternatives are significantly worse than the cryptographic method we use now than I don't see what choice we have in the matter. Edit: Is the problem cryptography in general, or just this particular method? Last fiddled with by jasong on 2012-02-24 at 04:24 2012-02-24, 04:32 #8 Zeta-Flux May 2003 7×13×17 Posts Quote:  Originally Posted by jasong Not to be a troll, but what sort of security could we have if we decided to only base things on proven assumptions? As I understand it, the only provably absolutely secure cryptosystem (currently, publicly known) is the use of one-time pads. But even that rests on the assumption that the enemy does not have access to those one-time pads, that the pads are sufficiently long, etc... which makes them ill-suited to internet security. 2012-02-24, 05:16 #9 retina Undefined "The unspeakable one" Jun 2006 My evil lair 5×1,223 Posts Quote:  Originally Posted by Zeta-Flux As I understand it, the only provably absolutely secure cryptosystem (currently, publicly known) is the use of one-time pads. But even that rests on the assumption that the enemy does not have access to those one-time pads, that the pads are sufficiently long, etc... which makes them ill-suited to internet security. There are schemes that are based upon a provably difficult problem to solve. But, as one would expect, they require far far too much overhead to be useful in any practical way. 2012-02-24, 15:07 #10 R.D. Silverman Nov 2003 22×5×373 Posts Quote:  Originally Posted by ewmayer Fascinating ... two comments: 1. "[Nash] is very well aware that this is a conjecture and that he cannot prove it. Surprisingly, for a mathematician, he does not even expect it to be solved. Even more surprisingly he seems quite comfortable designing his encryption system based on this unproven conjecture. This is quite eerily what modern cryptography does to this day: conjecture that some problem is computationally hard; not expect anyone to prove it; and yet base their cryptography on this unproven assumption." See: Neal Koblitz, "The Uneasy Relationship Between Mathematics and Cryptography", Notices AMS, Sept 2007. To say that it raised quite a stir is an understatement. Quote:  In the present case, we believe "hard" problems really are hard, but we have no proof as yet. We don't even know if one-way functions exist. Clearly if P = NP, then they do not. Quote:  So for a mathematician who also enjoys gambling (game theory), if someone did manage to find a polynomial-time way to crack some believed-to-be-hard (and hence all, if we are speaking of "hard" in the formal NP-complete sense) Actually, factoring is suspected to NOT be NP-complete. The existence of a sub-exponential algorithm is evidence for that. (but not a proof) Quote:  what would be the point of keeping Cocks' work classified? Is this just the usual paranoid-national-security apparatus M.O. of keeping as much stuff as possible classified for as long as possible, irrespective of the rationale for continued secrecy having vanished long ago? I will not speculate about such in public. 2012-02-25, 16:39 #11 lavalamp Oct 2007 Manchester, UK 17·79 Posts Quote:  Originally Posted by ewmayer I wonder whether this might be another example of the same phenomenon that came up recently with respect to the alleged discovery of faster-than-light particles at CERN. I immediately offered to bet anyone$1000 that the alleged discovery would vanish under scrutiny, on "win-win" strategy that most of the time such 'finds" do prove spurious - in which case there is no exciting 'new physics' but I win some money - but in the remote probability that the find is real, that will be cool enough that I won't mind losing the money.
http://xkcd.com/955/

 Similar Threads Thread Thread Starter Forum Replies Last Post pepi37 Math 0 2018-03-23 21:27 pepi37 Riesel Prime Search 18 2014-02-04 23:42 davieddy Soap Box 10 2012-04-01 03:43 davieddy Lounge 1 2011-01-20 21:22 mdettweiler Forum Feedback 25 2010-04-03 06:15

All times are UTC. The time now is 09:18.

Wed Apr 14 09:18:12 UTC 2021 up 6 days, 3:59, 0 users, load averages: 1.11, 1.50, 1.57

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.