John Nash on cryptography

1955 letters of John Nash and the NSA on a cryptosystem and Nash’s belief that near-perfect cryptography could exploit exponential difficulties.
cryptography, history
2012-02-222020-09-12 finished certainty: log importance: 4


The fol­low­ing tran­script was pre­pared from a with the declas­si­fied in 2012; I have attempted to repro­duce the math as exactly as pos­si­ble, and the lan­guage (cor­rect­ing spelling errors). ’s dia­grams are edited screen­shots from the PDF. Edi­to­r­ial notes, such as pages, are in brack­ets. All hyper­links are my own inser­tion. (The order­ing of sec­tions is roughly the same as the PDF but with a more log­i­cal order.) An was also cre­ated by Mike Rosulek in 2012.

The orig­i­nal Nash let­ters are on dis­play near the entrance of the National Cryp­to­logic Museum located next to NSA head­quar­ters in Fort Mead, Mary­land, as of 2016-09-22; the PDF scan does­n’t give a good impres­sion of how large Nash’s hand­writ­ing is, or how col­or­ful the dia­grams are. —Ed­i­tor

Primary

Nash

To Major Grosjean

[pg2] Dear Major Gros­jean,

I have writ­ten con­cern­ing the machine descrip­tion. This was hand­writ­ten and was sent to NSA late last spring, I believe, or sent to some­one there. Essen­tially the same machine descrip­tion was once sent to a Navy Com­mu­ni­ca­tion Cen­ter in Wash­ing­ton, I think.

I have dis­cussed the machine and gen­eral expo­nen­tial con­jec­ture with R.C. Blanch­field and A.M. Glea­son who have worked for NSA. Recently a con­ver­sa­tion with Prof. here indi­cated that he has recently been work­ing on a machine with sim­i­lar objec­tives. Since he will be con­sult­ing for NSA I shall [pg3] dis­cuss my ideas with him. He has devel­oped .

I hope my hand­writ­ing, etc. do not give the impres­sion I am just a crank or . My posi­tion here is Assist. Prof. of math. My best known work is in (reprint, sent sep­a­rate­ly). I men­tion these things only in the inter­est of secur­ing a most care­ful con­sid­er­a­tion of the machine and ideas by your most com­pe­tent asso­ci­ates.

If the machine descrip­tion does not turn up, I will pro­vide anoth­er. Also I shall be happy to pro­vide any addi­tional infor­ma­tion or answer any queries to the best of my abil­i­ty.

With many thanks for your prompt reply, I am

Sin­cerely Yours,

John Nash

Letter concerns enciphering

[pg4] Dear Sirs:

An enci­pher­ing-de­ci­pher­ing machine (in gen­eral out­line) of my inven­tion has been sent to your orga­ni­za­tion by way of the RAND cor­po­ra­tion. In this let­ter I make some remarks on a gen­eral prin­ci­ple rel­e­vant to enci­pher­ing in gen­eral and to my machine in par­tic­u­lar. This prin­ci­ple seems quite impor­tant to me, and I have some rea­son to believe you may not be fully aware of it.

Con­sider an enci­pher­ing process with a finite “key”, oper­at­ing on binary mes­sages. Specif­i­cal­ly, we can assume the process described by a func­tion

where the α’s, X’s, and Y’s are and where if Xi is changed, with the other X’s and α’s left fixed then Yi is changed.

[pg5] The α’s denote the “key” con­tain­ing r bits of infor­ma­tion. n is the max­i­mum span of the “mem­ory” of the process. If n were ∞ the argu­ments given below would not be basi­cally altered.

To con­sider the resis­tance of an enci­pher­ing process to being bro­ken we that at same times the enemy knows every­thing but the key being used and to break it needs only dis­cover the key from this infor­ma­tion.

We see imme­di­ately that in prin­ci­ple the enemy needs very lit­tle infor­ma­tion to begin to break down the process. Essen­tial­ly, as soon as r bits of enci­phered mes­sage have been trans­mit­ted the key is about deter­mined. This is no secu­ri­ty, for a prac­ti­cal key should not be too long. But this does not con­sider how easy or dif­fi­cult it is for the enemy to make the com­pu­ta­tion deter­min­ing the key. If this com­pu­ta­tion, [pg6] although pos­si­ble in prin­ci­ple, were suf­fi­ciently long at best then the process could still be secure in a prac­ti­cal sense.

The most direct com­pu­ta­tion pro­ce­dure would be for the enemy to try all 2r pos­si­ble keys, one by one. Obvi­ously this is eas­ily made imprac­ti­cal for the enemy by sim­ply choos­ing r large enough.

In many cruder types of enci­pher­ing, par­tic­u­larly those which are not auto-­cod­ing, such as sub­sti­tu­tion ciphers (let­ter for let­ter, let­ter pair for let­ter pair, triple for triple…) shorter means for com­put­ing the key are fea­si­ble, essen­tially because the key can be deter­mined piece meal, one sub­sti­tu­tion at a time.

So a log­i­cal way to clas­sify enci­pher­ing processes is by the way in which the com­pu­ta­tion length for the com­pu­ta­tion of the key increases with increas­ing length of the key. This is at best expo­nen­tial [pg7] and at worst, prob­a­bly a rel­a­tively small power of r, ar2 or ar3, as in sub­sti­tu­tion ciphers.

Now my gen­eral con­jec­ture is as fol­lows: For almost all suf­fi­ciently com­plex types of enci­pher­ing, espe­cially where the instruc­tions given by dif­fer­ent por­tions of the key inter­act com­plexly with each other in the deter­mi­na­tion of their ulti­mate effects on the enci­pher­ing, the mean [?] key com­pu­ta­tion length increases expo­nen­tially with the length of the key, or in other words, with the infor­ma­tion con­tent of the key.

The sig­nif­i­cance of this gen­eral con­jec­ture, assum­ing its truth, is easy to see. It means that it is quite fea­si­ble to design ciphers that are effec­tively unbreak­able. As ciphers become more sophis­ti­cated the game of cipher break­ing by skilled teams, etc., should become a thing of the past.

[pg8] The nature of this con­jec­ture is such that I can­not prove it, even for a spe­cial type of ciphers. Nor do I expect it to be proven. But this does not destroy its sig­nif­i­cance. The prob­a­bil­ity of the truth of the con­jec­ture can be guessed at on the basis of expe­ri­ence with enci­pher­ing and deci­pher­ing.

If qual­i­fied opin­ions incline to believe in the expo­nen­tial con­jec­ture, then I think we (the U.S.) can not afford not to make use of it. Also we should try to keep track of the progress of for­eign nations towards “unbreak­able” types of ciphers.

Since the U.S. pre­sum­ably does not want other nations to use ciphers we can­not expect to break, this gen­eral prin­ci­ple should prob­a­bly be stud­ied but kept secret.

I believe the enci­pher­ing-de­ci­pher­ing machine I invented and had trans­mit­ted to the N.S.A. via RAND has this “unbreak­able” prop­er­ty. In addi­tion it has sev­eral other advan­tages in that [pg9] the same phys­i­cal machine would func­tion both for cipher­ing and deci­pher­ing and that it is auto-­syn­chro­niz­ing and recov­ers after iso­lated errors in trans­mis­sion. These prop­er­ties are not typ­i­cal of enci­pher­ing sys­tems which are auto-­cod­ing. Also it is suit­able for an all elec­tron­ic, ultra rapid, embod­i­ment.


I do not expect any infor­ma­tive answer to this let­ter, yet it would be nice to have some sort of answer. I would be happy to explain more fully any­thing which is not clear in my let­ter, or to amplify on it.

I have been treat­ing my ideas as infor­ma­tion deserv­ing some secrecy pre­cau­tions, yet I feel it is impor­tant to com­mu­ni­cate them to the right peo­ple. I hope the mate­r­ial in this let­ter can obtain prompt con­sid­er­a­tion by very highly com­pe­tent men, versed in the field.

Sin­cere­ly.

John Nash

John Nash

Asst. Prof. Math.

Machine description

[pg12] E.M. Gib­son, Lt.­Col., AGC, Asst. Adj. Gen.

Dear Sir:

Here is a descrip­tion of my enci­pher­ing-de­ci­pher­ing machine.

The trans­mit­ting arrange­ment
The deci­pher­ing arrange­ment

In the receiv­ing arrange­ment the same com­po­nents are used except for the addi­tion of the retarder, which is a one-u­nit delay. The mes­sages are to be sequences of binary dig­its (num­bers ). The machines work on a cycling basis, per­form­ing cer­tain oper­a­tions [pg13] dur­ing each cycle.

Dur­ing each cycle the adder, A, takes in two dig­its and adds them and sends on the sum obtained from the pre­vi­ous addi­tion. The delay in this addi­tion neces­si­tates the retarder, R, in the receiv­ing cir­cuit.

The per­muter will be described in more detail below. It takes in a digit from D dur­ing each cycle and also puts out a num­ber. What it does, which is the choice between two per­mu­ta­tions is deter­mined by what digit (1 or 0) is in D at the time. The per­muter always has a num­ber of dig­its remem­bered within it. Each cycle it shuf­fles them around, chang­ing some 1’s to zeros, sends one digit on, and takes in a digit from D.

In oper­a­tion the input of the receiver is the out­put of the trans­mit­ter. So the input to R is the same as the input to D in the trans­mit­ter. Hence the out­put of P in the receiver is the same as the out­-put of P in the trans­mit­ter, except for a one-u­nit lag.

[pg14] So the adder A in the receiver gets: (1) the out­-put of A in the trans­mit­ter, and (2) the pre­vi­ous input from P(tran­s.) to A(tran­s). Now since binary addi­tion is the same as binary sub­trac­tion (i.e. + & - are the same) the out­put of A(re­ceiv.) will be the pre­vi­ous input to A(tran­s.) From the input to the trans­mit­ter, i.e., it will be the clear or unci­phered mes­sage.

The per­muter, P, and “decider”, D, work as fol­lows, illus­trated by exam­ple:

Per­mu­ta­tion exam­ple

[pg15] The cir­cles rep­re­sent places where a digit can be stored. Dur­ing each cycle either the red per­mu­ta­tion of dig­its or the blue takes place. This is decided by the digit in D at the begin­ning of the cycle. The D digit moves to the first cir­cle or stor­age place in P dur­ing the cycle after it has deter­mined the choice of the per­mu­ta­tion.

Both per­mu­ta­tions should cycle through all the places in P, so that a digit would be car­ried through all of them and out under its action alone.

In addi­tion to mov­ing dig­its around the per­mu­ta­tions can change 1’s to 0’s and v.v. For exam­ple

Shift digit left

rep­re­sents a shift of the digit in the left cir­cle to the right with this change

Change def­i­n­i­tion

[pg16] The “key” for the enci­pher­ing machine is the choice of the per­mu­ta­tions. If there are n stor­age points in P, not count­ing the first one, which receives the digit from D, then there are pos­si­ble keys.


I guess I can rely on your peo­ple to check on the pos­ses­sion of this machine of the var­i­ous prop­er­ties I claimed for it in a pre­vi­ous let­ter. I hope the cor­re­spon­dence I have sent in receives care­ful atten­tion from the most qual­i­fied peo­ple, because I think the basic points involved are very impor­tant.

Sin­cere­ly,

John Nash

Assist. Prof. Math.

P.S. Var­i­ous devices could be added to the machine, but I think it would gen­er­ally be bet­ter to enlarge the per­muter than to add any­thing. Of course error-­cor­rect­ing cod­ing could occa­sion­ally be a use­ful adjunct.

NSA

To Nash (1)

[pg10] Seri­al: 531

25 Jan 1955

Mr. John Nash
Depart­ment of Math­e­mat­ics
Mass­a­chu­setts Insti­tute of Tech­nol­ogy
Cam­bridge 39, Mass­a­chu­setts

Dear Mr. Nash:

Your recent let­ter, received 18 Jan­u­ary 1955, is not­ed. Tech­ni­cians at this Agency recall a very inter­est­ing dis­cus­sion with you which took place approx­i­mately four years ago, and will wel­come the oppor­tu­nity to exam­ine your ideas on the sub­ject of cryp­tog­ra­phy.

A check within this Agency has, unfor­tu­nate­ly, dis­closed no infor­ma­tion on your machine. A descrip­tion of the prin­ci­ples involved will be appre­ci­at­ed.

Sin­cere­ly,

E.M. Gib­son
Lt. Col., AGC
Assis­tant Adj. Gen.

cc: AG
C/S
COMSEC (3)
412

M/R: In Jan 1955, Mr. Nash offered gen­eral remarks on cryp­tog­ra­phy and requested eval­u­a­tion of descrip­tive mate­r­ial which he had for­warded through Rand Corp. NSA Ser 236, 12 Jan 55 informed Mr. Nash that the mate­r­ial had not arrived. Mr. Nash in let­ter rec’d 18 Jan 55 states the mate­r­ial was sent to NSA and to a Navy Com­mu­ni­ca­tion Cen­ter in Wash. late last spring. A check of Agency records and dis­cus­sions with var­i­ous indi­vid­u­als (R/D math­e­mati­cians and per­sons who might have had con­tact with Rand Cor­p.) within the Agency has uncov­ered noth­ing con­cern­ing the sys­tem. This cor­re­spon­dence requests a descrip­tion of the machine.

In 1950 Mr. Nash sub­mit­ted mate­ri­al, in inter­view, which was eval­u­ated by NSA as not suit­able.

[sig­na­ture]

M. A. Lyons, 4128, 60372, in

  1. K C/See 2-2 [?]

To Nash (2)

[pg11] Seri­al: 236

12 Jan 1955

Mr. John Nash
Depart­ment of Math­e­mat­ics
Mass­a­chu­setts Insti­tute of Tech­nol­ogy
Cam­bridge 39, Mass­a­chu­setts

Dear Mr. Nash:

Ref­er­ence is made to your recent let­ter con­cern­ing enci­pher­ing process­es. The infor­ma­tion regard­ing the gen­eral prin­ci­ples has been noted with inter­est. It will be con­sid­ered ful­ly, and par­tic­u­larly in con­nec­tion with your enci­pher­ing-de­ci­pher­ing machine.

The descrip­tion of your machine has not yet been received from the Rand Cor­po­ra­tion. As soon as details are received, the machine will be stud­ied to deter­mine whether it is of inter­est to the Gov­ern­ment.

The pre­sen­ta­tion for appraisal of your ideas for safe­guard­ing com­mu­ni­ca­tions secu­rity is very much appre­ci­at­ed.

Sin­cere­ly,

D.M. Gros­jean
Major WAC
Actg. Asst. Adju­tant Gen­eral

cc: AG
C/S
COMSEC (3)
412

M/R: Mr. Nash offers remarks on a gen­eral prin­ci­ple rel­e­vant to enci­pher­ing in gen­eral and to his machine in par­tic­u­lar. The machine, which he is send­ing via the Rand Cor­po­ra­tion, has not yet been received.

This let­ter informs Mr. Nash that his remarks are being noted and that the machine will be stud­ied as soon as details are received. This reply coor­di­nated with Mr. M. M. Math­ews, NSA-31. This is an interim reply.

[sig­na­ture]

M. A. Lyons, 4128, 30372, in

C/SEC 202

To Nash (3)

[pg17] Seri­al: 1358

3 Mar 1955

Mr. John Nash
Depart­ment of Math­e­mat­ics
Mass­a­chu­setts Insti­tute of Tech­nol­ogy
Cam­bridge 39, Mass­a­chu­setts

Dear Mr. Nash:

Ref­er­ence is made to your let­ter received in this Agency on 17 Feb­ru­ary 1955.

The sys­tem which you describe has been very care­fully exam­ined for pos­si­ble appli­ca­tion to mil­i­tary and other gov­ern­ment use. It has been found that the cryp­to­graphic prin­ci­ples involved in your sys­tem, although inge­nious, do not meet the nec­es­sary secu­rity require­ments for offi­cial appli­ca­tion.

Unfor­tu­nately it is impos­si­ble to dis­cuss any details in this let­ter. Per­haps in the future another oppor­tu­nity will arise for dis­cus­sion of your ideas on the sub­ject of cryp­tog­ra­phy.

Although your sys­tem can­not be adopt­ed, its pre­sen­ta­tion for appraisal and your gen­eros­ity in offer­ing it for offi­cial use are very much appre­ci­at­ed.

It is regret­ted that a more favor­able reply can­not be giv­en.

Sin­cere­ly,

E.M. Gib­son
Lt. Col., AGC
Assis­tant Adj. Gen.

cc: AG
C/S
COMSEC (3)
412

(M/R attached)

Internal

[pg18] M/R: In Jan 55 Mr. Nash offered gen­eral remarks on cryp­tog­ra­phy and requested val­u­a­tion of descrip­tive mate­r­ial which he had for­warded through Rand Corp. The Mate­r­ial was not received from Rand Corp. Dr. Cam­paigne received a let­ter from Mr. Nash enclos­ing a copy of the let­ter (5 Apr 54) from Rand which trans­mit­ted this mate­r­ial to NSA. This mate­r­ial was found in R/D files. In the mean­time Mr. Nash sent a hand­writ­ten descrip­tion of his enci­pher­ing-de­ci­pher­ing machine.

Mr. Nash pro­poses a per­mut­ing cipher-­text auto-key prin­ci­ple which has many of the desir­able fea­tures of a good auto-key sys­tem; but it affords only lim­ited secu­ri­ty, and requires a com­par­a­tively large amount of equip­ment. The prin­ci­ple would not be used alone in its present form and suit­able mod­i­fi­ca­tion or exten­sion is con­sid­ered unlike­ly, unless it could be used in con­junc­tion with other good auto-key prin­ci­ples.

This cor­re­spon­dence informs Mr. Nash that his sys­tem does not meet nec­es­sary secu­rity require­ments; and expresses plea­sure at the thought of an oppor­tu­nity to dis­cuss Mr. Nash’s ideas on cryp­tog­ra­phy again. Such a dis­cus­sion took place in 1950 when Mr. Nash sub­mit­ted mate­ri­al, in inter­view, which was eval­u­ated by NSA as unsuit­able.

An inter­est­ing pam­phlet on Non-­Co­op­er­a­tive Games1, writ­ten by Mr. Nash was also sent to this Agency by the author for our infor­ma­tion.

Dr. Cam­paigne has been informed that the reply has been writ­ten and is not inter­ested in fur­ther coor­di­na­tion.

[sig­na­ture]
M.A. Lyons, 4128/60372/rwb

Secondary

  • , NSA:

    When peo­ple hear the name “John Nash”, many recall the movie , in which actor por­trays the math­e­mat­i­cal genius whose game-the­ory research as a grad­u­ate stu­dent at Prince­ton Uni­ver­sity earned him the in 1994.

    The National Cryp­to­logic Muse­um’s newest exhibit, “An Inquis­i­tive Mind: John Nash Let­ters,” fea­tures copies of cor­re­spon­dence between Dr. Nash and the National Secu­rity Agency (NSA) from the 1950s when he was devel­op­ing his ideas on an encryp­tion-de­cryp­tion machine.

    At the height of his career in math­e­mat­ics, Dr. Nash wrote a series of let­ters to NSA, propos­ing ideas for such a machine. While the agency acknowl­edged his ideas, they were never adopt­ed. The let­ters were pre­served with NSA’s analy­sis in a col­lec­tion of unso­licited cor­re­spon­dence received in 1955.

  • Cryp­tog­ra­pher imple­mented Nash’s cryp­tosys­tem in Python and assigned an exam­i­na­tion to his class in 2012:

    Prob­lem 1-2. Cryp­tosys­tem pro­posal by Nash

    In the 1950s the math­e­mati­cian John Nash (now famous for his work on game the­o­ry, and also the sub­ject the movie A Beau­ti­ful Mind), pri­vately pro­posed to the National Secu­rity Agency (NSA) an idea for a cryp­tosys­tem. This pro­posal was just declas­si­fied (two weeks ago!); a copy of it is avail­able on the class web­site as Hand­out # 3, together with some rel­e­vant cor­re­spon­dence with the NSA. Note that this pro­posal was not accepted by the NSA, who said that it did­n’t meet their secu­rity require­ments.

    What rea­sons, if any, can you fig­ure out for this rejec­tion? (Note that this assign­ment is a bit of an open prob­lem! Do the best you can, and write up what you can fig­ure out. We don’t know the answer to this ques­tion our­selves…)

  • , David S. John­son 2012:

    The other famous math­e­mati­cian whose let­ters fore­shad­owed the the­ory of NP-­com­plete­ness was John Nash, Nobel Prize win­ner for Eco­nom­ics and sub­ject of both the book and the movie A Beau­ti­ful Mind. In 1955, Nash sent sev­eral hand­writ­ten let­ters about encryp­tion to the United States National Secu­rity Agen­cy, which were not declas­si­fied and made pub­licly avail­able until 2012 [1]. In them, he observes that for typ­i­cal key-based encryp­tion process­es, if the plain texts and encrypted ver­sions of some small num­ber of mes­sages are given, then the key is deter­mined. This is not tech­ni­cally cor­rect, since in addi­tion there must be suf­fi­cient entropy in the plain texts, but Nash’s argu­ments apply as well to the prob­lem of find­ing some key con­sis­tent with the encryp­tions. His cen­tral obser­va­tion was that even if the key is deter­mined, it still may not be easy to find.

    If the key is a binary string of length r, exhaus­tive search will work (as it did for Gödel), but takes time expo­nen­tial in r. For weak cryp­tosys­tems, such as sub­sti­tu­tion ciphers, there are faster tech­niques, tak­ing time or , but Nash con­jec­tured that “for almost all suf­fi­ciently com­plex types of enci­pher­ing”, run­ning time expo­nen­tial in the key length is unavoid­able.

    This con­jec­ture would imply that P ≠ NP, since the decryp­tion prob­lem he men­tions is poly­no­mi­al-­time equiv­a­lent to a prob­lem in NP: Given the data on plain and encrypted texts and a pre­fix x of a key, is there a key con­sis­tent with the encryp­tions which has x as a pre­fix? It is a stronger con­jec­ture, how­ev­er, since it would also rule out the pos­si­bil­ity that all prob­lems in NP can, for instance, be solved in time , which, although non-poly­no­mi­al, is also not what one typ­i­cally means by “expo­nen­tial”. Nash is also mak­ing a sub­sidiary claim that is in essence about the NP-hard­ness of a whole col­lec­tion of decryp­tion prob­lems. This lat­ter claim appears to be false. Nash pro­posed an encryp­tion scheme of the type he spec­i­fied, but the NSA observed in pri­vate notes that it pro­vided only lim­ited secu­ri­ty, and since the pub­li­ca­tion of the let­ters mod­ern researchers have found it easy to break [2]. Also, like Gödel, Nash did not make the leap from low-order poly­no­mial time to poly­no­mial time in gen­er­al. He did how­ev­er, cor­rectly fore­see the math­e­mat­i­cal dif­fi­culty of the P ver­sus NP prob­lem. He admit­ted that he could not prove his con­jec­ture, nor did he expect it to be proved, even if it were true.

  • Shiro Kawai imple­mented Nash’s sys­tem in Scheme.

  • Blog­gers on the sig­nif­i­cance of the let­ter:

    • Aaron Roth:

      In it, John Nash makes the dis­tinc­tion between poly­no­mial time and expo­nen­tial time, con­jec­tures that there are prob­lems that can­not be solved faster than in expo­nen­tial time, and uses this con­jec­ture as the basis on which the secu­rity of a cryp­tosys­tem (of his own design) relies. He also antic­i­pates that prov­ing com­plex­ity lower bounds is a dif­fi­cult math­e­mat­i­cal prob­lem…These let­ters pre­date even Gödel’s [1956] let­ter to Von Neu­mann, which goes into much less detail about com­plex­i­ty, and yet has also been taken to antic­i­pate com­plex­ity the­ory and the P vs. NP prob­lem.

    • Noam Nisan:

      He then goes on to put for­ward an amaz­ingly pre­scient analy­sis antic­i­pat­ing com­pu­ta­tional com­plex­ity the­ory as well as mod­ern cryp­tog­ra­phy. In the let­ter, Nash takes a step beyond (with­out men­tion­ing it) and pro­poses that secu­rity of encryp­tion be based on com­pu­ta­tional hard­ness—this is exactly the trans­for­ma­tion to made two decades later by the rest of the world (at least pub­licly…). He then goes on to explic­itly focus on the dis­tinc­tion between poly­no­mial time and expo­nen­tial time com­pu­ta­tion, a cru­cial dis­tinc­tion which is the basis of , but made only about a decade later by the rest of the world…He is very well aware of the impor­tance of this “con­jec­ture” and that it implies an end to the game played between code-de­sign­ers and code-break­ers through­out his­to­ry. Indeed, this is exactly the point of view of mod­ern cryp­tog­ra­phy…­Sur­pris­ing­ly, for a math­e­mati­cian, he does not even expect it to be solved. Even more sur­pris­ingly he seems quite com­fort­able design­ing his encryp­tion sys­tem based on this unproven con­jec­ture. This is quite eerily what mod­ern cryp­tog­ra­phy does to this day: con­jec­ture that some prob­lem is com­pu­ta­tion­ally hard; not expect any­one to prove it; and yet base their cryp­tog­ra­phy on this unproven assump­tion.

    • Markus Kroet­zsch:

      Some cau­tion is needed here…it seems clear to me that Nash did fore­see impor­tant ideas of mod­ern cryp­tog­ra­phy. This is great and deserves recog­ni­tion. How­ev­er, it seems also very clear that he did not fore­see (in fact: could not even imag­ine) mod­ern com­plex­ity the­o­ry. Why else would he say that he does not think that the expo­nen­tial hard­ness of the prob­lem could ever be proven? It is true that the com­pu­ta­tional hard­ness of key tasks in mod­ern cryp­tog­ra­phy is an unsolved prob­lem, but we have pow­er­ful tools to prove hard­ness results in many other cas­es. So if Nash had antic­i­pated com­plex­ity the­ory as such, then his remark would mean that he would also have fore­seen these dif­fi­cul­ties…Over­all, it seems clear that a pre­dic­tion of com­plex­ity the­ory or its cur­rent inca­pac­ity with respect to cryp­to­graphic prob­lems can­not be found in this text, which does by no means dimin­ish the orig­i­nal­ity of the remarks on cryp­tog­ra­phy. One could also grant him a cer­tain math­e­mat­i­cal intu­ition that some com­pu­ta­tional prob­lems could be inher­ently hard to solve, although I don’t see any hint that he believes that such hard­ness could ever become a pre­cise math­e­mat­i­cal prop­er­ty.

    • Geof­frey Wat­son agrees:

      This is very inter­est­ing as a his­tor­i­cal doc­u­ment, but not sure that it sup­ports the inter­pre­ta­tions being put on it…a rea­son­able his­tor­i­cal con­clu­sion is that these ideas were just going around in the usual way. The “con­jec­ture” is a pretty mud­dled bit of think­ing. It pre­sum­ably means that Nash thinks that there are such expo­nen­tially hard ciphers, but to con­vert “almost all suf­fi­ciently com­plex types of enci­pher­ing, espe­cially where the instruc­tions given by dif­fer­ent por­tions of the key inter­act com­plexly with each other in the deter­mi­na­tion of their ulti­mate effects on the enci­pher­ing” into a pre­scient antic­i­pa­tion of com­plex­ity the­ory is a big ask.

    • Philonus Atio com­ments that (as one might expect for early work):

      I broke it in about 1 hour and I’m no expert in crypt­analy­sis. It is weak.

    • Ani­mats sug­gests why the NSA may’ve rejected the sys­tem:

      What Nash seems to be describ­ing is a . This has poten­tial as a cryp­tosys­tem, but isn’t a very good one. As the NSA pointed out, it “affords only lim­ited secu­rity”. When Nash wrote this, had already devel­oped the the­ory that allowed gen­eral crypt­analy­sis of rotor-­type machines. But that was still highly clas­si­fied. Fried­man, of course, was respon­si­ble for break­ing the Japan­ese , plus many oth­ers. Before Fried­man, crypt­analy­sis was about guess­ing. After Fried­man, it was about num­ber crunch­ing.

      Fried­man was the head crypt­an­a­lyst at NSA at the time. Within NSA, it would have been known that a lin­ear feed­back shift reg­is­ter was a weak key gen­er­a­tor. So this idea was, prop­er­ly, reject­ed. At least NSA looked at it. Fried­man’s hard line on that sub­ject was “No new encryp­tion sys­tem is worth look­ing at unless it comes from some­one who has already bro­ken a very hard one.”

      The fact that a prob­lem is isn’t enough to make it a good key gen­er­a­tor. The , the first pub­lic-key cryp­tosys­tem pub­lished, is based on an NP-hard prob­lem. But, like many NP-hard prob­lems, it’s only NP-hard in the worst case. The aver­age case is only . ( prob­lems, and prob­lems which can be con­verted to a lin­ear pro­gram­ming prob­lem, are like that.) So that pub­lic-key sys­tem was cracked. We still don’t have cryp­tosys­tems which are prov­ably NP-hard for all cas­es. Fac­tor­ing and ellip­tic curves are as good as it gets, and there’s still the pos­si­bil­ity that a break­through could make fac­tor­ing easy.


  1. s are the best-­known areas of game the­o­ry, includ­ing such games as the and where Nash did almost all of his game the­ory work; results on s appeared lat­er, are more com­plex & hard­er, and accord­ingly are much more obscure.↩︎