John Nash’s Letter to the NSA

[Eugen Leitl]

http://agtb.wordpress.com/2012/02/17/john-nashs-letter-to-the-nsa/ 

John Nashbs Letter to the NSA

February 17, 2012 by Noam Nisan

The National Security Agency (NSA) has recently declassified an amazing
letter that John Nash sent to it in 1955.  It seems that around the year 1950
Nash tried to interest some US security organs (the NSA itself was only
formally formed only in 1952) in an encryption machine of his design, but
they did not seem to be interested.  It is not clear whether some of his
material was lost, whether they ignored him as a theoretical professor, or b
who knows b used some of his stuff but did not tell him.  In this
hand-written letter sent by John Nash to the NSA in 1955, he tries to give a
higher-level point of view supporting his design:

    In this letter I make some remarks on a general principle relevant to
enciphering in general and to my machine in particular.

He tries to make sure that he will be taken seriously:

    I hope my handwriting, etc. do not give the impression I am just a crank
or circle-squarer.  My position here is Assist. Prof. of Math.  My best known
work is in game theory (reprint sent separately).

He then goes on to put forward an amazingly prescient analysis anticipating
computational complexity theory as well as modern cryptography.  In the
letter, Nash takes a step beyond Shannonbs information-theoretic
formalization of cryptography (without mentioning it) and proposes that
security of encryption be based on computational hardness b this is exactly
the transformation to modern cryptography made two decades later by the rest
of the world (at least publiclyb&).  He then goes on to explicitly focus on
the distinction between polynomial time and exponential time computation, a
crucial distinction which is the basis of computational complexity theory,
but made only about a decade later by the rest of the world:

    So a logical way to classify enciphering processes is by t he way in
which the computation length for the computation of the key increases with
increasing length of the key. This is at best exponential and at worst
probably at most a relatively small power of r, ar^2 or ar^3, as in
substitution ciphers.

He conjectures the security of a family of encryption schemes.  While not
totally specific here, in todaybs words he is probably conjecturing that
almost all cipher functions (from some b not totally clear b class) are
one-way:

    Now my general conjecture is as follows: for almost all sufficiently
complex types of enciphering, especially where the instructions given by
different portions of the key interact complexly with each other in the
determination of their ultimate effects on the enciphering, the mean key
computation length increases exponentially with the length of the key, or in
other words, the information content of the key.

He is very well aware of the importance of this bconjectureb and that it
implies an end to the game played between code-designers and code-breakers
throughout history.  Indeed, this is exactly the point of view of modern
cryptography.

    The significance of this general conjecture, assuming its truth, is easy
to see.  It means that it is quite feasible to design ciphers that are
effectively unbreakable.  As ciphers become more sophisticated the game of
cipher breaking by skilled teams, etc., should become a thing of the past.

He 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.

    The nature of this conjecture is such that I cannot prove it, even for a
special type of ciphers.  Nor do I expect it to be proven.

All in all, the letter anticipates computational complexity theory by a
decade and modern cryptography by two decades.  Not bad for someone whose
bbest known work is in game theoryb.  It is hard not to compare this letter
to Goedelbs famous 1956 letter to von Neumann also anticipating complexity
theory (but not cryptography).  That both Nash and Goedel passed through
Princeton may imply that these ideas were somehow bin the airb there.

ht: this declassified letter seems to have been picked up by Ron Rivest who
posted it on his coursebs web-site, and was then blogged about (and G+ed) by
Aaron Roth.

Edit: Ron Rivest has implemented Nashbs cryptosystem in Python.  I wonder
whether modern cryptanalysis would be able to break it.