A Fascinating Letter

February 22, 2012

I’ve mentioned here before the close connection between mathematics and cryptography, especially the public key cryptography that is used, among other things, as the basis for the SSL/TLS protocols that secure Internet commerce.   The security of the system depends on the use of a “one way” function; that is, a function that is easy to compute, but whose inverse is very difficult to compute.  For example, finding the product of two large prime numbers is relatively easy, but factoring the resulting product to find the original primes is believed to be computationally infeasible, provided the numbers are large:  2048 bits or more.  The analysis of the minimum effort required to solve problems like this is the focus of computational complexity theory, which emerged in the 1960s and 1970s as the merger of ideas from computer science and mathematics.

The New Scientist reports that the  US National Security Agency [NSA] has recently declassified some fascinating correspondence [PDF], centering on a letter it received from John Nash in 1955, on the subject of encryption systems.  Readers may recognize the name; John Nash was the brilliant mathematician and game theorist, subject of Sylvia Nasar’s  1998 biography, A Beautiful Mind, and the 2001 film  of the same name.  He made very important contributions to game theory, especially, and was one of the winners of the 1994 Nobel Memorial Economics Prize on the basis of that work.  Unfortunately, as related in the biography, he struggled with schizophrenia most of his adult life.

Apparently, Nash had written to predecessor agencies of the NSA (formed in 1952) back in 1950, describing a cipher machine he had designed.  The 1955 letter was an attempt to re-start that conversation.  The letter, written in longhand, appears at first glance more like something written by a high-school student (with not very good penmanship), rather than by one of the most brilliant living mathematicians.  It has a fair sprinkling of misspelled and crossed-out words.  Nash himself writes:

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 was at MIT at the time, although he subsequently spent most of his time at Princeton.  It is also somewhat amusing that the reprint, enclosed almost as an afterthought, was of the work that won a Nobel Prize.)

What is striking about the letter is that Nash anticipates the core of computational complexity, a decade or two before it made a public appearance.  He proposes that the security of an encryption system is founded on the difficulty of the computation required to break it.

So a logical way to classify enciphering processes is by the 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, ar2, or ar3, as in substitution ciphers.

He conjectures that, with a sufficiently complex encryption function, the computation can be made of exponential difficulty.  Why does this matter?  He explains that, if the computation is difficult enough, the encryption can be made extremely secure as long as the key is long enough.

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.

He says that he can’t prove the conjecture, and in fact expresses doubt that it is provable.  (So far, he’s right about that.)  But it seems clear that he grasped the essence of the problem quite a while before it was generally realized.  I was very glad when I heard that he had won the Nobel Prize; he did not have an easy life, and his contributions deserved recognition.  I’m similarly glad to see this work emerge from the shadows.

More on LightSquared

February 21, 2012

A couple of days ago, I posted a note here about the FCC’s decision to suspend indefinitely its provisional approval of the broadband wireless service proposed by LightSquared, because of it potential interference with the operation of the Global Positioning System [GPS].  LightSquared has consistently claimed that interference was the fault of the GPS device manufacturers, because their designs did not include adequate protection against signals on nearby frequencies.

Ars Technica has a new article discussing the situation in more detail.  The article largely comes to the same conclusion I have: that, while there may be some truth in LightSquared’s claim, the disruption of the existing GPS ecosystem is too big a price to pay for the benefits the proposed system would bring.

FCC Says No to LightSquared

February 19, 2012

Last summer, I wrote here a couple of times about a controversy surrounding a proposed new broadband wireless Internet service, to be provided by a company called LightSquared.  The central issue was the possibility that the new system would cause interference problems with the Global Positioning System [GPS].  The new service was planned to use a slice of the frequency spectrum, originally intended for satellite telephone service, that is just below the frequencies used by GPS.  When the spectrum licenses were originally acquired by SkyTerra Communications, a predecessor company to LightSquared, the plan was to make connections primarily with satellite links, with some small ground stations to fill in holes in the coverage. The controversy has come about because LightSquared persuaded the Federal Communications Commission[FCC] to amend its license to allow a service based almost entirely on a network of 40,000 ground transmitters.

As I noted in my earlier posts, there have been a variety of studies proposed and carried out to asses the potential for interference.  The results have suggested that the interference problem is real, and might have a significant adverse effect on GPS users.  Now, according to articles at Ars Technica and the New York Times, the FCC has indefinitely suspended its provisional approval of the LightSquared system, following the release of a final report from the National Telecommunications and Information Administration, part of the Department of Commerce.

The Federal Communications Commission (FCC) said today that it will not approve LightSquared’s proposal to build a national 4G-LTE network, after testing showed that the network would interfere with most existing GPS devices.

The decision came swiftly after the National Telecommunications and Information Administration (NTIA) today warned the FCC that “LightSquared’s proposed mobile broadband network will impact GPS services and that there is no practical way to mitigate the potential interference at this time.”

LightSquared claims that the interference is primarily due to the poor design of existing GPS equipment, which does not adequately reject signals on nearby frequencies.  There probably is at least some truth in this; originally, the spectrum LightSquared proposed using was slated to be used for satellite-based services.  Like the signals from GPS satellites, these would have been relatively weak.  But the ground stations LightSquared proposed as part of its system would have produced signals about a billion times as strong as the GPS signals, making adequate filtering very difficult.

The company says that it still hopes to reach a mutually acceptable solution with the FCC, which has issued a request for comments on the NTIA letter.   I hope that they succeed, because the new broadband capacity would be valuable, but messing up the GPS, which is used for so many purposes, is a price too high.

Intel to Offer Transactional Memory

February 18, 2012

Back in September of last year, I wrote about the transactional memory hardware being used by IBM in the new Sequoia super-computer it is building for the Lawrence Livermore National Laboratory.  The technology is expected to make software development for parallel processing easier.  Now, according to an article at Ars Technica, Intel plans to bring transactional memory support to mainstream products, beginning with its Haswell chips, due to ship sometime next year.  In a blog post announcing the feature, which it calls TSX (Transaction Synchronization Extensions), Intel’s James Reinders explains the basic idea of TSX:

In a nutshell, Intel TSX provides a set of instruction set extensions that allow programmers to specify regions of code for transactional synchronization. Programmers can use these extensions to achieve the performance of fine-grain locking while actually programming using coarse-grain locks.

The post also gives an overview of how the new capabilities can be used.  TSX has two application interfaces.  The first, called Hardware Lock Elision [HLE] is intended to make easier  the porting of existing code, which may use locks.  It also makes it possible to have code that will work correctly on both older processors (which don’t support transactional memory) and Haswell.   The second, Restricted Transactional Memory [RTM], is intended primarily for new development, and provides more flexible structuring of transactions than is possible with HLE.

Although the idea of atomic transactions should be familiar to anyone who has developed relational data base applications, transactional memory is still pretty new.  The TSX capabilities that Intel will provide are very low-level (close to the hardware) functions.  Development of higher-level development tools that can take advantage of facilities like TSX is still in the early stages, but the work has started.  I think the development holds a lot of promise for easier development of software that can use highly parallel hardware effectively.

Update Monday, 20 February, 10:51 EST

Corrected the chip name to ‘Haswell’, rather than ‘Haskell’.  Thanks to Jim Cownie for the correction.

Firefox, Thunderbird Get Security Updates

February 18, 2012

The Mozilla organization has released new versions of its Firefox browser and Thunderbird E-mail client; in both cases the new version number is 10.0.2.  The updates fix a critical security vulnerability in the library used to render PNG graphics.   More information is available in the Release Notes for Thunderbird and for Firefox.

I recommend upgrading your system as soon as you conveniently can.  You can get the new version via the built-in update mechanism (Help / About/ Check for Updates), or you can download a complete installation package for Firefox or Thunderbird, ina variety of (human) languages.

Critical Updates for Java

February 16, 2012

Oracle has released its quarterly security fixes for Java.  The new Version 6 Update 31, addresses 14 identified security vulnerabilities; at least one of these is extremely serious, because it can be exploited remotely without a login.  (There is also a Version 7 Update 3 available for developers, with the same fixes.)  Further information is available in the Critical Patch Update Advisory.

The new version is available for almost all platforms: Linux, Windows, and Solaris.  Apple supplies its own versions of Java for Mac OS X; there is usually a time lag of at least a few days after Oracle releases a new version before an updated Mac version is available

Because of the security content of this release, if you have Java installed ono your system, I recommend that you install this update as soon as you conveniently can.  You can obtain the new version, including the browser plug-in, from the Java download page.  Windows users can also use automatic updates to get the new release.


%d bloggers like this: