Improved Decipherment of Homophonic Ciphers

Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1764–1768, October 25-29, 2014, Doha, Qatar. c⃝2014 Association for Computational Linguistics Improved Decipherment of Homophonic Ciphers Malte Nuhn and Julian Schamper and Hermann Ney Human Language Technology and Pattern Recognition Computer Science Department, RWTH Aachen University, Aachen, Germany <surname>@cs.rwth-aachen.de Abstract 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 challenging than the decipher- ment of the previously deciphered Zodiac- 408 cipher (length 408, 54 different sym- bols). To the best of our knowledge, this cipher has not been deciphered automati- cally before. 1 Introduction State-of-the-art statistical machine translation sys- tems use large amounts of parallel data to estimate translation models. However, parallel corpora are expensive and not available for every domain. Decipherment uses only monolingual data to train a translation model: Improving the core deci- pherment algorithms is an important step for mak- ing decipherment techniques useful for training practical machine translation systems. In this paper we present improvements to the beam search algorithm for deciphering homo- phonic substitution ciphers as presented in Nuhn et al. (2013). We show significant improvements in computation time on the Zodiac-408 cipher and show the first decipherment of part two of the Beale ciphers. 2 Related Work Regarding the decipherment of 1:1 substitution ci- phers, various works have been published: Most older papers do not use a statistical approach and instead define some heuristic measures for scoring candidate decipherments. Approaches like Hart (1994) and Olson (2007) use a dictionary to check if a decipherment is useful. Clark (1998) defines other suitability measures based on n-gram counts and presents a variety of optimization techniques like simulated annealing, genetic algorithms and tabu search. On the other hand, statistical ap- proaches for 1:1 substitution ciphers are published in the natural language processing community: Ravi and Knight (2008) solve 1:1 substitution ci- phers optimally by formulating the decipherment problem as an integer linear program (ILP) while Corlett and Penn (2010) solve the problem using A∗ search. Ravi and Knight (2011) report the first automatic decipherment of the Zodiac-408 ci- pher. They use a combination of a 3-gram lan- guage model and a word dictionary. As stated in the previous section, this work can be seen as an extension …

Content truncated to 500 words