http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf has interesting material on what seems to be post war cryptographic methods. In particular, there is material on expander graphs. This methodological material helps us understand the general report on Tunny, and its use of the so-called “multiple witnesses” theorem.

Pre war, Alan Turing is known to have studied graph theory, focusing specifically on mathematical physics. HE was exposed to methods that used pseudo randomness probabilities to measure the infrquent arrival rates of tiny particles. Modeling these processes using graph theory was a study topic of the era. By the time Turng is involved in cryptographic research involving counting problems he is applying the same random process theory when attacking enigma and the Tunny cipher.

In the referenced paper, the author explains how one uses graph theory to sample very large search spaces – such as those found in cryptographic problems where the number of potential solutions may be many times larger than the number of atoms in the universe. In this explanation we see how the idea of the statistical witness is applied. Specifically, when the search space is huge and yet a small probability of error is required we see how cryptographic methods apply graph theory. in short we understand how 1945 era GCCS thought about processes for finding a needle in a haystack. Or, as the article says finding the large elephant hidden in a large search space.

## About home_pw

Computer Programmer who often does network administration with focus on security servers. Sometimes plays at slot machine programming.