Paper: Improved Decipherment of Homophonic Ciphers

ACL ID D14-1184
Title Improved Decipherment of Homophonic Ciphers
Venue Conference on Empirical Methods in Natural Language Processing
Session Main Conference
Year 2014

In this paper, we present two improve- ments to the beam search approach for solving homophonic substitution ciphers presented in Nuhn et al. (2013): An im- proved rest cost estimation together with an optimized strategy for obtaining the or- der in which the symbols of the cipher are deciphered reduces the beam size needed to successfully decipher the Zodiac-408 cipher from several million down to less than one hundred: The search effort is re- duced from several hours of computation time to just a few seconds on a single CPU. These improvements allow us to success- fully decipher the second part of the fa- mous Beale cipher (see (Ward et al., 1885) and e.g. (King, 1993)): Having 182 differ- ent cipher symbols while having a length of just 762 symbols, the decipherment is way more challen...