Tuesday, February 28, 2012

A Mind in Non-Polynomial Time Was Once Beautiful

Leave it to The Best Men

Ah, The Bureaucracy. It sho ain't about the stinkin' Ingenuity thing.
Posted by at
Labels: , , , , , , , , ,

4 comments:

Tecumseh said...

It has been found that the cryptographic principles involved in your system, although ingenious, do not meet the necessary security requirements for official application.

How do you say dummkopf in English?

2/28/2012 11:41 PM
Tecumseh said...

By the way, one of those fellows Nash mentions -- R.C. Blanchfield -- wrote his thesis (on knot theory) at Princeton in the early fifties, and published two papers in the Annals, after which he gave up on math.

2/28/2012 11:48 PM
Tecumseh said...

An interesting comment:

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 Shannon's information-theoretic formalization of cryptography (without mentioning it) and proposes that security of encryption be based on computational hardness — this is exactly the transformation to modern cryptography made two decades later by the rest of the world (at least publicly…). 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...He is very well aware of the importance of this “conjecture” 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...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.

2/29/2012 12:00 AM
Tecumseh said...

Counterpoint:

What Nash seems to be describing is a linear feedback shift register. This has potential as a cryptosystem, but isn't a very good one. As the NSA pointed out, it "affords only limited security". When Nash wrote this, Friedman had already developed the theory that allowed general cryptanalysis of rotor-type machines. But that was still highly classified. Friedman, of course, was responsible for breaking the Japanese "Purple" cipher, plus many others. Before Friedman, cryptanalysis was about guessing. After Friedman, it was about number crunching.

Friedman was the head cryptanalyst at NSA at the time. Within NSA, it would have been known that a linear feedback shift register was a weak key generator. So this idea was, properly, rejected. At least NSA looked at it. Friedman's hard line on that subject was "No new encryption system is worth looking at unless it comes from someone who has already broken a very hard one."

Note that Friedman was from Chişinău. Duh.

2/29/2012 12:05 AM

Post a Comment

Subscribe to: Post Comments (Atom)