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
by: John Nash 2012-02-222020-09-12 finished certainty: log importance: 4


The fol­low­ing tran­script was pre­pared from a with the de­clas­si­fied in 2012; I have at­tempted to re­pro­duce the math as ex­actly as pos­si­ble, and the lan­guage (cor­rect­ing spelling er­rors). ’s di­a­grams are edited screen­shots from the PDF. Ed­i­to­r­ial notes, such as pages, are in brack­ets. All hy­per­links are my own in­ser­tion. (The or­der­ing of sec­tions is roughly the same as the PDF but with a more log­i­cal or­der.) An was also cre­ated by Mike Ro­sulek in 2012.

The orig­i­nal Nash let­ters are on dis­play near the en­trance of the Na­tional Cryp­to­logic Mu­seum lo­cated 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 im­pres­sion of how large Nash’s hand­writ­ing is, or how col­or­ful the di­a­grams are. —Ed­i­tor

Primary

Nash

To Major Grosjean

[pg2] Dear Ma­jor Gros­jean,

I have writ­ten con­cern­ing the ma­chine de­scrip­tion. This was hand­writ­ten and was sent to NSA late last spring, I be­lieve, or sent to some­one there. Es­sen­tially the same ma­chine de­scrip­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 ma­chine and gen­eral ex­po­nen­tial con­jec­ture with R.C. Blanch­field and A.M. Glea­son who have worked for NSA. Re­cently a con­ver­sa­tion with Prof. here in­di­cated that he has re­cently been work­ing on a ma­chine with sim­i­lar ob­jec­tives. Since he will be con­sult­ing for NSA I shall [pg3] dis­cuss my ideas with him. He has de­vel­oped .

I hope my hand­writ­ing, etc. do not give the im­pres­sion I am just a crank or . My po­si­tion here is As­sist. Prof. of math. My best known work is in (reprint, sent sep­a­rate­ly). I men­tion these things only in the in­ter­est of se­cur­ing a most care­ful con­sid­er­a­tion of the ma­chine and ideas by your most com­pe­tent as­so­ci­ates.

If the ma­chine de­scrip­tion does not turn up, I will pro­vide an­oth­er. Also I shall be happy to pro­vide any ad­di­tional in­for­ma­tion or an­swer any queries to the best of my abil­i­ty.

With many thanks for your prompt re­ply, I am

Sin­cerely Yours,

John Nash

Letter concerns enciphering

[pg4] Dear Sirs:

An en­ci­pher­ing-de­ci­pher­ing ma­chine (in gen­eral out­line) of my in­ven­tion has been sent to your or­ga­ni­za­tion by way of the RAND cor­po­ra­tion. In this let­ter I make some re­marks on a gen­eral prin­ci­ple rel­e­vant to en­ci­pher­ing in gen­eral and to my ma­chine in par­tic­u­lar. This prin­ci­ple seems quite im­por­tant to me, and I have some rea­son to be­lieve you may not be fully aware of it.

Con­sider an en­ci­pher­ing process with a fi­nite “key”, op­er­at­ing on bi­nary mes­sages. Specifi­cal­ly, we can as­sume the process de­scribed 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 de­note the “key” con­tain­ing r bits of in­for­ma­tion. n is the max­i­mum span of the “mem­ory” of the process. If n were ∞ the ar­gu­ments given be­low would not be ba­si­cally al­tered.

To con­sider the re­sis­tance of an en­ci­pher­ing process to be­ing bro­ken we that at same times the en­emy knows every­thing but the key be­ing used and to break it needs only dis­cover the key from this in­for­ma­tion.

We see im­me­di­ately that in prin­ci­ple the en­emy needs very lit­tle in­for­ma­tion to be­gin to break down the process. Es­sen­tial­ly, as soon as r bits of en­ci­phered mes­sage have been trans­mit­ted the key is about de­ter­mined. This is no se­cu­ri­ty, for a prac­ti­cal key should not be too long. But this does not con­sider how easy or diffi­cult it is for the en­emy to make the com­pu­ta­tion de­ter­min­ing the key. If this com­pu­ta­tion, [pg6] al­though pos­si­ble in prin­ci­ple, were suffi­ciently long at best then the process could still be se­cure in a prac­ti­cal sense.

The most di­rect com­pu­ta­tion pro­ce­dure would be for the en­emy to try all 2r pos­si­ble keys, one by one. Ob­vi­ously this is eas­ily made im­prac­ti­cal for the en­emy by sim­ply choos­ing r large enough.

In many cruder types of en­ci­pher­ing, par­tic­u­larly those which are not au­to-cod­ing, such as sub­sti­tu­tion ci­phers (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, es­sen­tially be­cause the key can be de­ter­mined piece meal, one sub­sti­tu­tion at a time.

So a log­i­cal way to clas­sify en­ci­pher­ing processes is by the way in which the com­pu­ta­tion length for the com­pu­ta­tion of the key in­creases with in­creas­ing length of the key. This is at best ex­po­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 ci­phers.

Now my gen­eral con­jec­ture is as fol­lows: For al­most all suffi­ciently com­plex types of en­ci­pher­ing, es­pe­cially where the in­struc­tions given by differ­ent por­tions of the key in­ter­act com­plexly with each other in the de­ter­mi­na­tion of their ul­ti­mate effects on the en­ci­pher­ing, the mean [?] key com­pu­ta­tion length in­creases ex­po­nen­tially with the length of the key, or in other words, with the in­for­ma­tion con­tent of the key.

The sig­nifi­cance of this gen­eral con­jec­ture, as­sum­ing its truth, is easy to see. It means that it is quite fea­si­ble to de­sign ci­phers that are effec­tively un­break­able. As ci­phers be­come more so­phis­ti­cated the game of ci­pher break­ing by skilled teams, etc., should be­come a thing of the past.

[pg8] The na­ture of this con­jec­ture is such that I can­not prove it, even for a spe­cial type of ci­phers. Nor do I ex­pect it to be proven. But this does not de­stroy its sig­nifi­cance. The prob­a­bil­ity of the truth of the con­jec­ture can be guessed at on the ba­sis of ex­pe­ri­ence with en­ci­pher­ing and de­ci­pher­ing.

If qual­i­fied opin­ions in­cline to be­lieve in the ex­po­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 na­tions to­wards “un­break­able” types of ci­phers.

Since the U.S. pre­sum­ably does not want other na­tions to use ci­phers we can­not ex­pect to break, this gen­eral prin­ci­ple should prob­a­bly be stud­ied but kept se­cret.

I be­lieve the en­ci­pher­ing-de­ci­pher­ing ma­chine I in­vented and had trans­mit­ted to the N.S.A. via RAND has this “un­break­able” prop­er­ty. In ad­di­tion it has sev­eral other ad­van­tages in that [pg9] the same phys­i­cal ma­chine would func­tion both for ci­pher­ing and de­ci­pher­ing and that it is au­to-syn­chro­niz­ing and re­cov­ers after iso­lated er­rors in trans­mis­sion. These prop­er­ties are not typ­i­cal of en­ci­pher­ing sys­tems which are au­to-cod­ing. Also it is suit­able for an all elec­tron­ic, ul­tra rapid, em­bod­i­ment.


I do not ex­pect any in­for­ma­tive an­swer to this let­ter, yet it would be nice to have some sort of an­swer. I would be happy to ex­plain more fully any­thing which is not clear in my let­ter, or to am­plify on it.

I have been treat­ing my ideas as in­for­ma­tion de­serv­ing some se­crecy pre­cau­tions, yet I feel it is im­por­tant to com­mu­ni­cate them to the right peo­ple. I hope the ma­te­r­ial in this let­ter can ob­tain 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 de­scrip­tion of my en­ci­pher­ing-de­ci­pher­ing ma­chine.

The trans­mit­ting arrange­ment
The de­ci­pher­ing arrange­ment

In the re­ceiv­ing arrange­ment the same com­po­nents are used ex­cept for the ad­di­tion of the re­tarder, which is a one-u­nit de­lay. The mes­sages are to be se­quences of bi­nary dig­its (num­bers ). The ma­chines work on a cy­cling ba­sis, per­form­ing cer­tain op­er­a­tions [pg13] dur­ing each cy­cle.

Dur­ing each cy­cle the adder, A, takes in two dig­its and adds them and sends on the sum ob­tained from the pre­vi­ous ad­di­tion. The de­lay in this ad­di­tion ne­ces­si­tates the re­tarder, R, in the re­ceiv­ing cir­cuit.

The per­muter will be de­scribed in more de­tail be­low. It takes in a digit from D dur­ing each cy­cle and also puts out a num­ber. What it does, which is the choice be­tween two per­mu­ta­tions is de­ter­mined by what digit (1 or 0) is in D at the time. The per­muter al­ways has a num­ber of dig­its re­mem­bered within it. Each cy­cle it shuffles them around, chang­ing some 1’s to ze­ros, sends one digit on, and takes in a digit from D.

In op­er­a­tion the in­put of the re­ceiver is the out­put of the trans­mit­ter. So the in­put to R is the same as the in­put to D in the trans­mit­ter. Hence the out­put of P in the re­ceiver is the same as the out­-put of P in the trans­mit­ter, ex­cept for a one-u­nit lag.

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

The per­muter, P, and “de­cider”, D, work as fol­lows, il­lus­trated by ex­am­ple:

Per­mu­ta­tion ex­am­ple

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

Both per­mu­ta­tions should cy­cle through all the places in P, so that a digit would be car­ried through all of them and out un­der its ac­tion alone.

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

Shift digit left

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

Change de­fi­n­i­tion

[pg16] The “key” for the en­ci­pher­ing ma­chine 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 re­ceives 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 ma­chine 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 re­ceives care­ful at­ten­tion from the most qual­i­fied peo­ple, be­cause I think the ba­sic points in­volved are very im­por­tant.

Sin­cere­ly,

John Nash

As­sist. Prof. Math.

P.S. Var­i­ous de­vices could be added to the ma­chine, but I think it would gen­er­ally be bet­ter to en­large the per­muter than to add any­thing. Of course er­ror-cor­rect­ing cod­ing could oc­ca­sion­ally be a use­ful ad­junct.

NSA

To Nash (1)

[pg10] Se­ri­al: 531

25 Jan 1955

Mr. John Nash
De­part­ment of Math­e­mat­ics
Mass­a­chu­setts In­sti­tute of Tech­nol­ogy
Cam­bridge 39, Mass­a­chu­setts

Dear Mr. Nash:

Your re­cent let­ter, re­ceived 18 Jan­u­ary 1955, is not­ed. Tech­ni­cians at this Agency re­call a very in­ter­est­ing dis­cus­sion with you which took place ap­prox­i­mately four years ago, and will wel­come the op­por­tu­nity to ex­am­ine your ideas on the sub­ject of cryp­tog­ra­phy.

A check within this Agency has, un­for­tu­nate­ly, dis­closed no in­for­ma­tion on your ma­chine. A de­scrip­tion of the prin­ci­ples in­volved will be ap­pre­ci­at­ed.

Sin­cere­ly,

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

cc: AG
C/S
COMSEC (3)
412

M/R: In Jan 1955, Mr. Nash offered gen­eral re­marks on cryp­tog­ra­phy and re­quested eval­u­a­tion of de­scrip­tive ma­te­r­ial which he had for­warded through Rand Corp. NSA Ser 236, 12 Jan 55 in­formed Mr. Nash that the ma­te­r­ial had not ar­rived. Mr. Nash in let­ter rec’d 18 Jan 55 states the ma­te­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 in­di­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 un­cov­ered noth­ing con­cern­ing the sys­tem. This cor­re­spon­dence re­quests a de­scrip­tion of the ma­chine.

In 1950 Mr. Nash sub­mit­ted ma­te­ri­al, in in­ter­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] Se­ri­al: 236

12 Jan 1955

Mr. John Nash
De­part­ment of Math­e­mat­ics
Mass­a­chu­setts In­sti­tute of Tech­nol­ogy
Cam­bridge 39, Mass­a­chu­setts

Dear Mr. Nash:

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

The de­scrip­tion of your ma­chine has not yet been re­ceived from the Rand Cor­po­ra­tion. As soon as de­tails are re­ceived, the ma­chine will be stud­ied to de­ter­mine whether it is of in­ter­est to the Gov­ern­ment.

The pre­sen­ta­tion for ap­praisal of your ideas for safe­guard­ing com­mu­ni­ca­tions se­cu­rity is very much ap­pre­ci­at­ed.

Sin­cere­ly,

D.M. Gros­jean
Ma­jor WAC
Actg. Asst. Ad­ju­tant Gen­eral

cc: AG
C/S
COMSEC (3)
412

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

This let­ter in­forms Mr. Nash that his re­marks are be­ing noted and that the ma­chine will be stud­ied as soon as de­tails are re­ceived. This re­ply co­or­di­nated with Mr. M. M. Math­ews, NSA-31. This is an in­terim re­ply.

[sig­na­ture]

M. A. Lyons, 4128, 30372, in

C/SEC 202

To Nash (3)

[pg17] Se­ri­al: 1358

3 Mar 1955

Mr. John Nash
De­part­ment of Math­e­mat­ics
Mass­a­chu­setts In­sti­tute of Tech­nol­ogy
Cam­bridge 39, Mass­a­chu­setts

Dear Mr. Nash:

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

The sys­tem which you de­scribe has been very care­fully ex­am­ined for pos­si­ble ap­pli­ca­tion to mil­i­tary and other gov­ern­ment use. It has been found that the cryp­to­graphic prin­ci­ples in­volved in your sys­tem, al­though in­ge­nious, do not meet the nec­es­sary se­cu­rity re­quire­ments for offi­cial ap­pli­ca­tion.

Un­for­tu­nately it is im­pos­si­ble to dis­cuss any de­tails in this let­ter. Per­haps in the fu­ture an­other op­por­tu­nity will arise for dis­cus­sion of your ideas on the sub­ject of cryp­tog­ra­phy.

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

It is re­gret­ted that a more fa­vor­able re­ply can­not be giv­en.

Sin­cere­ly,

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

cc: AG
C/S
COMSEC (3)
412

(M/R at­tached)

Internal

[pg18] M/R: In Jan 55 Mr. Nash offered gen­eral re­marks on cryp­tog­ra­phy and re­quested val­u­a­tion of de­scrip­tive ma­te­r­ial which he had for­warded through Rand Corp. The Ma­te­r­ial was not re­ceived from Rand Corp. Dr. Cam­paigne re­ceived a let­ter from Mr. Nash en­clos­ing a copy of the let­ter (5 Apr 54) from Rand which trans­mit­ted this ma­te­r­ial to NSA. This ma­te­r­ial was found in R/D files. In the mean­time Mr. Nash sent a hand­writ­ten de­scrip­tion of his en­ci­pher­ing-de­ci­pher­ing ma­chine.

Mr. Nash pro­poses a per­mut­ing ci­pher-text au­to-key prin­ci­ple which has many of the de­sir­able fea­tures of a good au­to-key sys­tem; but it affords only lim­ited se­cu­ri­ty, and re­quires 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 ex­ten­sion is con­sid­ered un­like­ly, un­less it could be used in con­junc­tion with other good au­to-key prin­ci­ples.

This cor­re­spon­dence in­forms Mr. Nash that his sys­tem does not meet nec­es­sary se­cu­rity re­quire­ments; and ex­presses plea­sure at the thought of an op­por­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 ma­te­ri­al, in in­ter­view, which was eval­u­ated by NSA as un­suit­able.

An in­ter­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 au­thor for our in­for­ma­tion.

Dr. Cam­paigne has been in­formed that the re­ply has been writ­ten and is not in­ter­ested in fur­ther co­or­di­na­tion.

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

Secondary

  • , NSA:

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

    The Na­tional Cryp­to­logic Mu­se­um’s newest ex­hibit, “An In­quis­i­tive Mind: John Nash Let­ters,” fea­tures copies of cor­re­spon­dence be­tween Dr. Nash and the Na­tional Se­cu­rity Agency (NSA) from the 1950s when he was de­vel­op­ing his ideas on an en­cryp­tion-de­cryp­tion ma­chine.

    At the height of his ca­reer in math­e­mat­ics, Dr. Nash wrote a se­ries of let­ters to NSA, propos­ing ideas for such a ma­chine. While the agency ac­knowl­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 un­so­licited cor­re­spon­dence re­ceived in 1955.

  • Cryp­tog­ra­pher im­ple­mented Nash’s cryp­tosys­tem in Python and as­signed an ex­am­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 fa­mous 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 Na­tional Se­cu­rity Agency (NSA) an idea for a cryp­tosys­tem. This pro­posal was just de­clas­si­fied (two weeks ago!); a copy of it is avail­able on the class web­site as Hand­out # 3, to­gether with some rel­e­vant cor­re­spon­dence with the NSA. Note that this pro­posal was not ac­cepted by the NSA, who said that it did­n’t meet their se­cu­rity re­quire­ments.

    What rea­sons, if any, can you fig­ure out for this re­jec­tion? (Note that this as­sign­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 an­swer to this ques­tion our­selves…)

  • , David S. John­son 2012:

    The other fa­mous math­e­mati­cian whose let­ters fore­shad­owed the the­ory of NP-com­plete­ness was John Nash, No­bel 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 en­cryp­tion to the United States Na­tional Se­cu­rity Agen­cy, which were not de­clas­si­fied and made pub­licly avail­able un­til 2012 [1]. In them, he ob­serves that for typ­i­cal key-based en­cryp­tion process­es, if the plain texts and en­crypted ver­sions of some small num­ber of mes­sages are given, then the key is de­ter­mined. This is not tech­ni­cally cor­rect, since in ad­di­tion there must be suffi­cient en­tropy in the plain texts, but Nash’s ar­gu­ments ap­ply as well to the prob­lem of find­ing some key con­sis­tent with the en­cryp­tions. His cen­tral ob­ser­va­tion was that even if the key is de­ter­mined, it still may not be easy to find.

    If the key is a bi­nary string of length r, ex­haus­tive search will work (as it did for Gödel), but takes time ex­po­nen­tial in r. For weak cryp­tosys­tems, such as sub­sti­tu­tion ci­phers, there are faster tech­niques, tak­ing time 𝒪(r2) or 𝒪(r3), but Nash con­jec­tured that “for al­most all suffi­ciently com­plex types of en­ci­pher­ing”, run­ning time ex­po­nen­tial in the key length is un­avoid­able.

    This con­jec­ture would im­ply that P ≠ NP, since the de­cryp­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 en­crypted texts and a pre­fix x of a key, is there a key con­sis­tent with the en­cryp­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 in­stance, be solved in time , which, al­though non-poly­no­mi­al, is also not what one typ­i­cally means by “ex­po­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 de­cryp­tion prob­lems. This lat­ter claim ap­pears to be false. Nash pro­posed an en­cryp­tion scheme of the type he spec­i­fied, but the NSA ob­served in pri­vate notes that it pro­vided only lim­ited se­cu­ri­ty, and since the pub­li­ca­tion of the let­ters mod­ern re­searchers have found it easy to break [2]. Al­so, 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 diffi­culty of the P ver­sus NP prob­lem. He ad­mit­ted that he could not prove his con­jec­ture, nor did he ex­pect it to be proved, even if it were true.

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

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

    • Aaron Roth:

      In it, John Nash makes the dis­tinc­tion be­tween poly­no­mial time and ex­po­nen­tial time, con­jec­tures that there are prob­lems that can­not be solved faster than in ex­po­nen­tial time, and uses this con­jec­ture as the ba­sis on which the se­cu­rity of a cryp­tosys­tem (of his own de­sign) re­lies. He also an­tic­i­pates that prov­ing com­plex­ity lower bounds is a diffi­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 de­tail about com­plex­i­ty, and yet has also been taken to an­tic­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 an­tic­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 be­yond (with­out men­tion­ing it) and pro­poses that se­cu­rity of en­cryp­tion be based on com­pu­ta­tional hard­ness—this is ex­actly 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 ex­plic­itly fo­cus on the dis­tinc­tion be­tween poly­no­mial time and ex­po­nen­tial time com­pu­ta­tion, a cru­cial dis­tinc­tion which is the ba­sis of , but made only about a decade later by the rest of the world…He is very well aware of the im­por­tance of this “con­jec­ture” and that it im­plies an end to the game played be­tween code-de­sign­ers and code-break­ers through­out his­to­ry. In­deed, this is ex­actly 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 ex­pect it to be solved. Even more sur­pris­ingly he seems quite com­fort­able de­sign­ing his en­cryp­tion sys­tem based on this un­proven 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 ex­pect any­one to prove it; and yet base their cryp­tog­ra­phy on this un­proven as­sump­tion.

    • Markus Kroet­zsch:

      Some cau­tion is needed here…it seems clear to me that Nash did fore­see im­por­tant ideas of mod­ern cryp­tog­ra­phy. This is great and de­serves 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 ex­po­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 un­solved prob­lem, but we have pow­er­ful tools to prove hard­ness re­sults in many other cas­es. So if Nash had an­tic­i­pated com­plex­ity the­ory as such, then his re­mark would mean that he would also have fore­seen these diffi­cul­ties…Over­all, it seems clear that a pre­dic­tion of com­plex­ity the­ory or its cur­rent in­ca­pac­ity with re­spect to cryp­to­graphic prob­lems can­not be found in this text, which does by no means di­min­ish the orig­i­nal­ity of the re­marks on cryp­tog­ra­phy. One could also grant him a cer­tain math­e­mat­i­cal in­tu­ition that some com­pu­ta­tional prob­lems could be in­her­ently hard to solve, al­though I don’t see any hint that he be­lieves that such hard­ness could ever be­come a pre­cise math­e­mat­i­cal prop­er­ty.

    • Ge­offrey Wat­son agrees:

      This is very in­ter­est­ing as a his­tor­i­cal doc­u­ment, but not sure that it sup­ports the in­ter­pre­ta­tions be­ing put on it…a rea­son­able his­tor­i­cal con­clu­sion is that these ideas were just go­ing 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 ex­po­nen­tially hard ci­phers, but to con­vert “al­most all suffi­ciently com­plex types of en­ci­pher­ing, es­pe­cially where the in­struc­tions given by differ­ent por­tions of the key in­ter­act com­plexly with each other in the de­ter­mi­na­tion of their ul­ti­mate effects on the en­ci­pher­ing” into a pre­scient an­tic­i­pa­tion of com­plex­ity the­ory is a big ask.

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

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

    • An­i­mats sug­gests why the NSA may’ve re­jected the sys­tem:

      What Nash seems to be de­scrib­ing is a lin­ear feed­back shift reg­is­ter. This has po­ten­tial as a cryp­tosys­tem, but is­n’t a very good one. As the NSA pointed out, it “affords only lim­ited se­cu­rity”. When Nash wrote this, had al­ready de­vel­oped the the­ory that al­lowed gen­eral crypt­analy­sis of ro­tor-type ma­chines. But that was still highly clas­si­fied. Fried­man, of course, was re­spon­si­ble for break­ing the Japan­ese , plus many oth­ers. Be­fore 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, re­ject­ed. At least NSA looked at it. Fried­man’s hard line on that sub­ject was “No new en­cryp­tion sys­tem is worth look­ing at un­less it comes from some­one who has al­ready bro­ken a very hard one.”

      The fact that a prob­lem is is­n’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 av­er­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 el­lip­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 ar­eas of game the­o­ry, in­clud­ing such games as the and where Nash did al­most all of his game the­ory work; re­sults on s ap­peared lat­er, are more com­plex & hard­er, and ac­cord­ingly are much more ob­scure.↩︎