Decipherment as Regression: Solving Historical Substitution Ciphers by Learning Symbol Recurrence Relations
Nishant Kambhatla, Logan Born, Anoop Sarkar · 2023
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.1