Paper: Solving Substitution Ciphers with Combined Language Models

ACL ID C14-1218
Title Solving Substitution Ciphers with Combined Language Models
Venue International Conference on Computational Linguistics
Session Main Conference
Year 2014
Authors

We propose a novel approach to deciphering short monoalphabetic ciphers that combines both character-level and word-level language models. We formulate decipherment as tree search, and use Monte Carlo Tree Search (MCTS) as a fast alternative to beam search. Our experiments show a significant improvement over the state of the art on a benchmark suite of short ciphers. Our approach can also handle ciphers without spaces and ciphers with noise, which allows us to explore its applications to unsupervised transliteration and deniable encryption.