Breaking substitution cipher with language model

Question

Frequency analysis is a common tool used to break substitution ciphers, but often relies on intuition and guesswork of a human. Since language models can objectively calculate perplexity (how surprising a piece of language seems), they seem like a good way to formalize this process.

If I could run the calculate the perplexity of the ciphertext under each substitution, I would just pick the one with the lower perplexity. Since this is the least surprising out of the possibilities of the original text, it is likely to be the real original text. However since there are 26^26 different options, doing this with brute force is not possible.

Is there any more efficient way to find the best substitution? In particular, the substitution of letters that minimizes perplexity? This seems to be the same task that gradient descent tries to solve, but the problem here is that I don't think I can calculate the gradient.

Answer 1

Your question is a good one—and one that cryptographers have thought about a lot. The answer is yes!

First things first: the number of options isn’t quite $26^{26}$, because some of those ciphers wouldn’t be invertible. For instance, you could map every letter to Q, but how do you decode that? So the number is only(!) $26!$ possibilities.

That’s still astronomically large, but human cryptographers can break these codes from just a few examples. What’s the trick? They look at relative frequencies of letters and what makes for natural plaintext.

This seems to be the same task that gradient descent tries to solve…

Well, you’ve got a point that we’d like to optimize something. We can use some form of local search to improve the goodness of our mapping.

One method proposed for this is described in Hasinoff (2003); I think the paper is pretty approachable compared to a lot of the neural LM based papers coming out for this problem. To optimize, they use a popular technique called hill-climbing. (More specifically, stochastic hill climbing with random restarts—they never mention hill climbing in the paper, though.) The idea is to start with some initial (arbitrary) mapping and measure its perplexity as you suggested. Then loop to improve the perplexity. Pick some pair of letters and swap their mapping. Did this version reduce perplexity? If so, keep it. If not, don’t. Now make another swap, and so on, and so on.