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

Findings of the Association for Computational Linguistics: EACL 2023, pages 2136–2152 May 2-6, 2023 ©2023 Association for Computational Linguistics Decipherment as Regression: Solving Historical Substitution Ciphers by Learning Symbol Recurrence Relations Nishant Kambhatla Logan Born Anoop Sarkar School of Computing Science, Simon Fraser University 8888 University Drive, Burnaby BC, Canada {nkambhat, loborn, anoop}@sfu.ca 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 deci- pherment key using a character-level language model to constrain the search space. This work instead frames decipherment as a sequence pre- diction 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 decipher- ment 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 anal- ysis shows that the model learns recurrence relations between cipher symbols and recovers decipherment keys in its self-attention.1 1 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 distribu- tion. 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 recur- rent symbols to crack the cipher? In this work, we exploit this idea for decipher- ment by building upon recent successes of Trans- former models (Vaswani et al., 2017) in reasoning- based regression tasks such as mathematical rea- soning (Saxton et al., 2019; Li et al., 2021) and learning the mathematical function for recurrent 1https://github.com/protonish/decipher_symbol_ recurrence Figure 1: The homophonic substitution key for the Sime- one de Crema written in Mantua in 1401 AD. The top line maps each character in the alphabet to its reversed- alphabet equivalent; each vowel is substituted by three additional symbols. sequences (D’Ascoli et al., 2022). We rethink deci- pherment 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)2, in the form of encrypted let- ters 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. Fig- ure 1 shows the first known homophonic cipher from 1401 AD 3. Automated computational deci- pherment of such texts is challenging (Pettersson and Megyesi, 2019; Megyesi et al., 2020). 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) (Knight et al., …

Content truncated to 500 words