mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2012-02-19, 18:23   #1
Christenson
 
Christenson's Avatar
 
Dec 2010
Monticello

5·359 Posts
Default 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
Christenson is offline   Reply With Quote
Old 2012-02-19, 20:28   #2
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

1118610 Posts
Default

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?
ewmayer is offline   Reply With Quote
Old 2012-02-19, 20:48   #3
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

125178 Posts
Default

Quote:
Originally Posted by ewmayer View Post
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.
retina is online now   Reply With Quote
Old 2012-02-20, 03:08   #4
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

854810 Posts
Default

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".
LaurV is offline   Reply With Quote
Old 2012-02-20, 07:29   #5
xilman
Bamboozled!
 
xilman's Avatar
 
May 2003
Down not across

100111000110002 Posts
Default

Quote:
Originally Posted by ewmayer View Post
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.
xilman is offline   Reply With Quote
Old 2012-02-20, 15:13   #6
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts
Default

Quote:
Originally Posted by xilman View Post
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.)
Dubslow is offline   Reply With Quote
Old 2012-02-24, 04:23   #7
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

66618 Posts
Default

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
jasong is offline   Reply With Quote
Old 2012-02-24, 04:32   #8
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

7×13×17 Posts
Default

Quote:
Originally Posted by jasong View Post
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.
Zeta-Flux is offline   Reply With Quote
Old 2012-02-24, 05:16   #9
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

5×1,091 Posts
Default

Quote:
Originally Posted by Zeta-Flux View Post
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.
retina is online now   Reply With Quote
Old 2012-02-24, 15:07   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×7×53 Posts
Default

Quote:
Originally Posted by ewmayer View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2012-02-25, 16:39   #11
lavalamp
 
lavalamp's Avatar
 
Oct 2007
London, UK

1,297 Posts
Default

Quote:
Originally Posted by ewmayer View Post
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/
lavalamp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Nash value pepi37 Math 0 2018-03-23 21:27
Nash weight of base 17 pepi37 Riesel Prime Search 18 2014-02-04 23:42
Open letter to Bob davieddy Soap Box 10 2012-04-01 03:43
4 letter game davieddy Lounge 1 2011-01-20 21:22
Disappearance two-letter words mdettweiler Forum Feedback 25 2010-04-03 06:15

All times are UTC. The time now is 03:57.

Sun Jun 7 03:57:34 UTC 2020 up 74 days, 1:30, 0 users, load averages: 0.97, 0.99, 1.01

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

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.