Decipherment as Regression: Solving Historical Substitution Ciphers by Learning Symbol Recurrence Relations (2023)

Abstract: Solving substitution ciphers involves mapping sequences of cipher symbols to fluent text in a target language. This has conventionally been formulated as a search problem, to find the decipherment key using a character-level language model to constrain the search space. This work instead frames decipherment as a sequence prediction task, using a Transformer-based causal language model to learn recurrences between characters in a ciphertext. We introduce a novel technique for transcribing arbitrary substitution ciphers into a common recurrence encoding. By leveraging this technique, we (i) create a large synthetic dataset of homophonic ciphers using random keys, and (ii) train a decipherment model that predicts the plaintext sequence given a recurrence-encoded ciphertext. Our method achieves strong results on synthetic 1:1 and homophonic ciphers, and cracks several real historic homophonic ciphers. Our analysis shows that the model learns recurrence relations between cipher symbols and recovers decipherment keys in its self-attention.

## introduction text may be considered a special kind of recurrent sequence, where letters repeat at intervals which conform to a language's character n-gram distribution. the hidden mapping between cipher text and plain text can be viewed as a model that predicts this recurrent sequence. can we use self-attention to recover the mapping from a sequence of recurrent symbols to crack the cipher? in this work, we exploit this idea for decipherment by building upon recent successes of transformer models @xcite in reasoningbased regression tasks such as mathematical reasoning @xcite and learning the mathematical function for recurrent sequences @xcite . we rethink decipherment as a regression task that predicts a natural language plaintext by learning a recurrence relation between integer-coded ciphertext symbols. there exist large collections of historical ciphers (see de-crypt.org) foot_1 , in the form of encrypted letters and more informal communications, of which many remain undeciphered. many of these texts employ complex homophonic substitution ciphers, which mask the frequencies of letters by using a larger alphabet than the underlying language. figure 1 shows the first known homophonic cipher from 1401 ad foot_2 . automated computational decipherment of such texts is challenging @xcite . prior work has mainly focused on using clever heuristics and/or search algorithms to explore the space of cipher keys and score multiple candidate plaintexts under character language models (lms) @xcite @xcite @xcite @xcite in contrast @xcite train a sequence-tosequence model to solve simple (one-to-one) substitution ciphers. this approach, however, cannot solve complex homophonic ciphers as it relies on frequency information which such ciphers obscure. in this paper, in a departure from frequency and heuristic search-based techniques, we make the following contributions: 1 we create a sequenceto-sequence dataset comprising 2 million unique homophonic ciphers and their plaintext. 2 we propose a novel recurrence encoding which encodes information about the position and repetition of symbols in a cipher. this can be applied to both 1:1 and homophonic ciphers. 3 this encoding allows us to treat decipherment as a sequence prediction task conditioned on an integer sequence. we introduce a novel approach to solving homophonic ciphers by using a transformer lm to translate integer-encoded ciphertexts to plaintexts. we also provide exhaustive analysis to show the strengths of our model. 4 we demonstrate near-perfect results on synthetic homophonic ciphers. additionally, we show fully automated decipherment of tna_sp106/5 and bnf-f01, two real historical ciphers. ## decipherment of substitution ciphers a 1:1 or simple substitution cipher, the oldest known technique for obscuring written information, defines a 1-1 mapping between plaintext characters and ciphertext symbols. this mapping can easily be broken with frequency analysis @xcite 2021) which leverages the fact that these ciphers preserve the distribution of character frequencies in the underlying language. homophonic ciphers are substitution ciphers where one plaintext character may be encoded by more than one ciphertext symbol. in this way, frequent plaintext characters can be mapped to many infrequent ciphertext symbols, resulting in a flattened frequency distribution (figure 2 ). ## our generative decipherment model we frame decipherment as a novel sequence generation task-we train a generative language model that learns the relations between recurring symbols in a homophonic cipher and generates the corresponding deciphered plaintext message. ## homophonic substitution ciphers we experiment on solving our own synthetic homophonic ciphers, and on automatically deciphering two real world homophonic ciphers that have previously only been cracked manually. ## does our technique generalize to 1:1 substitution ciphers? to exploit the well-known weakness of simple substituion ciphers, aldarrab and may (2021) proposed frequency ranking whereby cipher symbols are replaced by their frequency ranks across all 1-1 substitution ciphers. we use recurrence encoding and frequency ranking with our best performing causal lm architecture foot_7 and compare with several baselines, including @xcite . our model performs well on simple substitutions ( ## unknown plaintext language as @xcite reports, several historical ciphers in libraries and archives have no information on the plaintext language. we evaluate on the latin borg cipher 11 , a ca. 17th century manuscript, to learn if our model can decipher without explicit knowledge of the underlying language. ser (%) multilingual seq2seq (2021) 5.47 multilingual causal lm (ours) 4.10 ## other related work computational decipherment based techniques have seen a wide range of applications ranging such as identifying unknown languages and scripts @xcite , writing systems @xcite @xcite and lost languages @xcite , offensive langauge detection @xcite , and, more recently, towards improving neural machine translation @xcite . while decipherment has strong connections to cryptography research, we limit the scope of this work to natural language based decipherment. @xcite proposed an unsupervised noisy channel based technique for decipherment. hauer et al. 2014 solved short ciphers with monte-carlo tree search. @xcite train a seq-to-seq lstm to solve polyalphabetic substitution ciphers including enigma, but only explore supervised knownplaintext attacks. ciphergan @xcite exploits learned letter embedding distributions, but requires a large volume of ciphertext and only handles 1:1 substitution and vigenère ciphers. @xcite and @xcite pro-pose techniques to decipher undersegmented ciphers. @xcite train a sequenceto-sequence neural translation model to decipher from character frequencies. in contrast, we introduce a novel encoding which is suitable for homophonic inputs, and demonstrate that a causal lm is more effective than a seq-to-seq model in a homophonic setting. cross-attention from encoder-decoder architectures has been shown to have limited explanatory power in translation settings @xcite . in spite of this, @xcite show that encoder self-attention implicitly captures information which replicates expert intuitions about document structure in an undeciphered script. in a similar vein, our key recovery experiments offer evidence of yet another way self-attention may be fruitfully exploited in the decoder in a decipherment setting. ## conclusion and future work we introduce a novel recurrence encoding to represent distributional information which is invariant across plaintexts and ciphertexts, even under homophonic ciphers. this allows us to train a transformer lm for decipherment using synthetic ciphertext-plaintext pairs. our model achieves strong results on unseen homophonic substitution ciphers, and achieves the first fully-automatic decipherment of several historical ciphers. we show that language models vastly outperform sequenceto-sequence models on this task, and that causal attention masking (which forces our model to reproduce the ciphertext before deciphering it) is crucial to solve homophonic inputs. our analysis shows that our model implicitly learns homophony relations and the decipherment key while reproducing the input. in a zero-shot setting, our model accurately deciphers into latin despite being trained on english; this work marks a successful departure from search-based solutions to homophonic substitution ciphers, and introduces language models as a viable tool for future decipherment work.