# Who first applied hill climbing algorithms to cryptanalysis?

As you may know, classical ciphers are now often broken with hill-climbing algorithms. The earliest mention of them in cryptography I could find occurs in some 1980s publication mentioning 1979 PhD thesis of M. Hellman's student Dov Andelman titled "Maximum Likelihood Estimation Applied to Cryptanalysis" (available at ProQuest):

This thesis analyzes a hill-climbing approach to cryptanalysis based on the maximum likelihood estimation technique from statistics. Rotor machines and S-P networks are used as examples.

The thesis (which, BTW, doesn't appear to use "hill climbing" terminology) lacks a proper literature review section, but it has a reference to prior work on p. 4:

If the continuous estimate [of "intermediate" key value — I. A.] yields a point near the true key point, we can determine the exact value of the true key by quantizing it. This idea was originally suggested by James Reeds of the University of California at Berkeley. Independently, Bahl [3], used a similar approach for a COA of simple substitution ciphers.

I haven't got the full thesis to check but the reference appear to link to a 1977 conference abstract by Lalit Bahl titled "An Algorithm for Solving Simple Substitution Cryptograms" which is available at the Internet Archive. The author iteratively refines a monoalphabetic substitution matrix by forwards-backwards algorithm until, if I understood correctly, the bigram (2-letter) frequencies match those of the ciphertext (some Pr{Y}, where Y is the ciphertext, appears to be used as fitness function). Does that qualify as hill climbing?

Finally, in 1982 Andelman and Reeds published an article "On the Cryptanalysis of Rotor Machines and Substitution-Permutation Networks" (available on Academia) roughly following the aforementioned thesis. I didn't find anything new there, but noted they didn't reference Bahl.

In retrospect it may look like quite obvious to apply hill-climbing algorithms (in use since 1960s at least) to cryptanalysis, IMHO, so the natural question is whether there were earlier attempts which I wasn't able to find.

I also checked declassified CIA archives, but unfortunately they appear to contain nothing on the topic.

So taking all the available evidence into account, who can be said to first use hill climbing in cryptanalysis?

If you define hill-climbing as using some kind of fitness function (KL Divergence, conditional probability, whatever) and exploring the function's value locally towards a maximum, the Bahl paper would be such an early example. I wasn't aware of it, though I knew about the Andelman/Reeds paper.

Whether it is the first may be hard to say. I had a quick look at declassified NSA articles, including some from the NSA Technical Journal articles here. Interestingly, there are bayesian papers, including the paper by I.J. Good on the so-called Good-Turing score, but found no specific papers related to local search mechanisms.

Interestingly, the paper "The Strength of the Bayes Score" available here is heavily redacted, presumably with respect to specific application scenarios.

Thanks for the internet archive link, by the way. This 1977 IEEE International Symposium on Information Theory must have been one of the first including cryptology related papers.

I think you can go digging further at the declassified NSA website, I did not search through the other publications there.

• I'm preparing a history of cryptography talk that might touch on how BP affected/effected the adoption of Bayesian statistics. Is there a good way to contact you? Jan 13 at 20:05
• [email protected] Jan 13 at 21:02

If one takes a loose definition of hillclimbing to mean making a sequence of small perturbations to form a sequence of incrementally improving solutions, early approaches to solving the Playfair cipher fall into this category. In chapter XXI of her classic work Cryptanalysis (Dover pp 204-5) Helen Fouche Gaines writes:

Another good demonstration, provided the student has access to it in his public library is Colonel Parker Hitt's "Manual for the Solution of Military Ciphers." [...] Colonel Hitt's demonstration begins with the usual pair-count, made on a chart. He selects from this chart the (approximately) ten letters having the widest variety of contact, including, if necessary, the vowel or so which would have to be present in a keyword; and these letters are assumed to have stood on the upper rows of the key square. The remaining (approximately) fifteen letters are then set up in their alphabetical sequence and are assumed to have stood on the lower rows in about that order. They are not, of course, known to be correctly placed; the set-up merely gives a concrete ideas as to where letters ought to have stood [...] With a few obvious identifications made in the usual way, letters begin to arrange themselves in the upper rows, and a gradual adjustment takes place which corrects the few wrong assumptions of the lower rows.

Colonel Hitt published his work in 1916. I have it on order and shall report further on reading.